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