무역로

시간 제한4초메모리 제한1024 MB

요약

트리의 각 노드에 이익이 주어질 때, 질의마다 지정된 나라를 모두 지나는 단순 경로 중 이익 합이 최대인 값을 구합니다. 그런 경로가 없으면 No를 출력합니다.

난이도: 어려움10점 중 8점
유형: 트리, DFS, 동적 계획법
정답자: 아직 제출이 없습니다

문제

여러분은 서방에서 가장 명성이 높은 상인이다. 최근 국제 정세가 바뀌면서, 새로운 시장을 개척하기 위해 동방의 나라들을 순회하는 무역로를 건설하려고 계획하고 있다.

동방에는 $1$ 번부터 $N$ 번까지 번호가 붙은 $N$ 개의 나라가 있고, 나라 사이를 잇는 도로가 $N-1$ 개 있다. 모든 도로는 서로 다른 두 나라를 양방향으로 잇고, 주어진 도로만으로 임의의 두 나라 사이를 이동할 수 있다. 즉, 동방의 나라들은 트리 형태로 연결되어 있다.

무역로는 임의의 두 나라를 잇는 단순 경로이다. 무역을 시작할 나라와 끝낼 나라는 자유롭게 정할 수 있다. 무역로의 수익은 무역로에 포함된 모든 나라에서 얻는 무역 수익의 합이다. $i$ 번 나라의 무역 수익은 $A_i$ 이다.

여러분은 $Q$ 개의 무역로 건설 계획을 세웠다. 각 계획에는 무역로가 반드시 지나야 하는 나라 $K_i$ 개의 목록이 포함되어 있다. 각 계획마다 주어진 나라를 모두 지나는 무역로 중 최대 수익을 구하라. 그러한 무역로가 없으면 No를 출력한다.

입력

첫째 줄에 나라의 수 $N$ 과 무역로 건설 계획의 수 $Q$ 가 공백을 두고 주어진다. ( $3 \le N \le 500000$ , $1 \le Q \le 500000$ )

다음 $N-1$ 개의 줄에는 도로가 잇는 두 나라의 번호 $u_i$ 와 $v_i$ 가 공백을 두고 주어진다. ( $1 \le u_i < v_i \le N$ )

그다음 줄에는 $A_1, A_2, \dots, A_N$ 이 공백을 두고 주어진다. $A_i$ 는 $i$ 번 나라를 지나는 무역로를 건설했을 때 얻는 수익이다. ( $-10^9 \le A_i \le 10^9$ )

다음 $Q$ 개의 줄에는 $K_i, S_1, S_2, \dots, S_{K_i}$ 가 공백을 두고 주어진다. $K_i$ 는 $i$ 번째 계획에서 무역로가 반드시 지나야 하는 나라의 수이고, $S_j$ 는 그러한 나라의 번호이다. ( $1 \le K_i \le N$ , $1 \le S_j \le N$ , $j \ne k$ 이면 $S_j \ne S_k$ , $\sum_{i=1}^{Q} K_i \le 500000$ )

입력에 주어지는 모든 수는 정수이다.

출력

각 계획마다 그 계획의 나라를 모두 지나는 무역로 중 최대 수익을 한 줄에 하나씩 출력한다. 그러한 무역로가 없으면 No를 출력한다.

예제3

예제 1

입력

9 5
1 2
1 3
2 4
2 5
2 6
3 7
7 8
3 9
10 -3 5 -7 0 2 -11 9 5
1 1
3 9 2 7
2 2 3
6 6 2 1 3 7 8
3 3 4 5

예상 출력

20
No
19
12
No

예제 2
입력
```
4 1
1 2
2 3
2 4
5 -4 6 3
1 2
```
예상 출력
```
7
```

예제 3

입력

3 7
1 2
1 3
-10 -20 -40
1 1
1 2
1 3
2 1 2
2 1 3
2 2 3
3 1 3 2

예상 출력

-10
-20
-40
-30
-50
-70
-70