17231번 - 이건 버그야! 서브태스크

상민이와 지수가 전쟁 시뮬레이션 게임을 한다. 게임에는 N개의 지역이 있으며, 각 지역은 전투력을 가지고 있다. 지역들은 N-1개의 길로 연결되어있으며, 연결된 지역 사이를 이동할 수 있다. 모든 지역이 하나의 방향 없는 트리구조를 이루고 있어 임의의 지역에서 다른 지역으로 언제나 이동할 수 있다.

게임 한 판은 다음과 같이 진행된다.

1. 상민이는 먼저 하나의 지역을 골라 요새를 설치한다.
2. 지수는 요새가 설치되지 않은 지역을 골라 자신의 선봉으로 지정한다. 선봉의 전방은 상민이의 요새를 향하는 방향이다.
3. 지수의 선봉의 후방 지역들은 모두 지수의 세력에 편입되어 선봉과 함께 상민이의 요새를 공격한다.
4. 상민이의 요새는 지수의 공격을 막는다. 요새의 전방은 지수의 공격이 들어오는 방향이다.
5. 상민이의 요새의 후방 지역들은 모두 상민이의 세력에 편입되어 지수의 공격을 막는다.
6. 지수의 전투력이 상민이의 전투력보다 크다면 지수가 승리하고, 그렇지 않다면 패배한다.

<그림 1> 지수의 세력 예시 (예제1)

각 세력의 전투력은 다음과 같이 계산된다.

$$\sum_{u\in\text{세력}} A_u\times(\max_{v\in\text{세력}}(dist(P, v)) - dist(P, u) + 1) $$

여기서 P는 플레이어가 각 세력의 요새 혹은 선봉으로 지정한 지역, dist(a,b)는 a 지역과 b 지역 간 거리이다.

예를들어, <그림 1> 에서 지수의 세력은 {(2) × 1} + {(3) × 2} + {(8 + 6 + 1) × 3} + {(2 + 7) × 4} + {(4) × 5} + {(5) × 6} = 139 의 전투력을 갖는다.

이 게임의 고인물인 지수는 게임에 버그가 있음을 알고 있다. 게임 내 전투력의 자료형이 unsigned int로 구현되어, 세력의 전투력이 2³²-1을 넘어가는 순간 오버플로우가 발생해 0부터 다시 시작하게 되는 것이다. 이 버그를 잘 이해하고 있는 지수는 버그를 적극 활용해 상민이로부터 대승을 거두고자 한다.

첫 줄에는 지역의 개수 N, 진행될 게임의 횟수 Q가 주어진다.

두 번째 줄부터 N-1 줄에 걸쳐 지역 간 길의 정보를 나타내는 u, v (1 ≤ u, v ≤ N) 가 주어진다. 이는 u번 지역과 v번 지역이 연결되어있다는 의미이다.

N+1번째 줄에는 각 지역의 전투력 A_i (1 ≤ i ≤ N) 가 1번 지역부터 N개에 걸쳐 차례로 주어진다.

N+2번째 줄부터 Q 줄에 걸쳐 각 판마다 상민이가 요새를 설치한 지역의 번호 x (1 ≤ x ≤ N) 가 주어진다.

Q 줄에 걸쳐 각 판마다 상민이가 요새를 설치한 지역의 번호가 x (1 ≤ x ≤ N) 일 때, 지수가 선봉을 지정하여 얻을 수 있는 "지수의 전투력 - 상민이의 전투력"의 최댓값을 한 줄씩 출력한다.

• 1 ≤ Q ≤ 100,000
• 0 ≤ A_i < 2³²

• 2 ≤ N ≤ 100

• 2 ≤ N ≤ 100,000