← 返回题目列表

AtCoder · nadafes2022_day1_h

H. 旅行 PCT 问题

中文机器翻译题面 查看原题

配点 : 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