H - Traveling PCT Problem Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

NPCA 王国には N 個の町と N-1 個の道があります。i 番目の道は長さが 1 で、町 u_i と町 v_i を双方向に結んでいます。また、どの町からどの町へもいくつかの道路を通ることで移動することができます。

クエリが Q 個与えられます。i 番目のクエリは以下です。

旅人の PCT 君が、好きな町を出発し、K_i 個の町 A_{i,1},A_{i,2},\ldots,A_{i,K_i} を訪れ、好きな町で旅を終えるとき、移動する距離の最小値を求めよ。ただし、訪れる順番は何でもよい。

最短距離で移動したい PCT 君のために、Q 個のクエリをすべて処理してください。

制約

  • 2 \leq N \leq 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq u_i < v_i \leq N
  • 与えられるグラフは木
  • 2 \leq K_i
  • \sum_{i=1}^{Q}K_i \leq 2\times 10^5
  • 1 \leq A_{i,1} < A_{i,2} < \ldots < A_{i,K_i} \leq N
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N Q
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}
K_1 A_{1,1} A_{1,2} \ldots A_{1,K_1}
K_2 A_{2,1} A_{2,2} \ldots A_{2,K_2}
\vdots
K_Q A_{Q,1} A_{Q,2} \ldots A_{Q,K_Q}

出力

Q 行出力せよ。i\,(1 \leq i \leq Q) 行目には、i 番目のクエリに対する答えを出力せよ。

入力例 1

3 2
1 2
2 3
2 1 2
3 1 2 3

出力例 1

1
2

2 番目のクエリでは、例えば町 3 を出発して町 3 →町 2 →町 1 と移動すれば移動距離は 2 です。

入力例 2

2 1
1 2
2 1 2

出力例 2

1

入力例 3

6 4
2 5
3 5
1 4
4 5
4 6
3 1 2 3
3 2 4 5
2 1 6
6 1 2 3 4 5 6

出力例 3

5
2
2
7