配点:7 点
問題文
N 有一棵顶点树,顶点编号为 1, 2, \cdots, N 。i 番目 (1 \leq i \leq N-1) 条边为边 A_i 和 按字典顺序比较 B_i 。
,将给出以下形式的查询 Q 个,请按j = 1, 2, \cdots, Q 的顺序回答。
- N-1 从所有的边中选择一些作为保留的边。
- 删除未被选择的边时,边缘 V_{j,1},V_{j,2}, \cdots ,V_{j,K_j} 希望所有边都互相连接。
- 最少需要选择多少条边?
制約
- 2 \leq N \leq 100000
- 1 \leq A_i \lt B_i \leq N
- 1 \leq Q \leq 100000
- 2 \leq K_j \leq N
- 1 \leq V_{j,1} \lt V_{j,2} \lt \cdots \lt V_{j,K_j} \leq N
- K_1 + K_2 + \cdots + K_Q \leq 200000
- 给定的图是树
- 所有输入均为整数
小课题·得点
这个问题可以分解为若干小课题,如果所有小课题的测试用例都正确,则被视为“完成了此小课题”。
提交的源码得分为已正确回答的小课题分数之和。
- (2 点):N,Q \leq 5000
- (1 点):K_j = 2
- (1 点):K_j = 3
- (3分):没有额外的否定。
入力
输入是按以下格式从标准输入给出的。
N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}
Q
K_1 V_{1,1} V_{1,2} ... V_{1,K_1}
K_2 V_{2,1} V_{2,2} ... V_{2,K_2}
\vdots
K_Q V_{Q,1} V_{Q,2} ... V_{Q,K_Q}
出力
j=1,2,...,Q , 您可以获得j 线 j 请输出对第几条质问的回答。
入力例 1
6 1 2 2 3 3 4 1 5 3 6 5 2 1 2 3 1 3 5 4 2 3 4 5 5 1 2 3 5 6 6 1 2 3 4 5 6
出力例 1
1 3 4 4 5
1 在第n个询问中,顶点 1 与边缘 2 是
您也可以写 1 因为第n条边相邻,所以只需选择这一条边即可。
对其余的询问也能以同样方式得出答案。
另外,该输入符合小课题1、4的否定条件。
入力例 2
6 1 2 2 3 3 4 1 5 3 6 5 2 1 2 2 3 4 2 4 6 2 1 5 2 2 5
出力例 2
1 1 2 1 2
这个输入满足小课题1、2、4的否定条件。
入力例 3
6 1 2 2 3 3 4 1 5 3 6 5 3 1 2 3 3 1 2 5 3 1 3 6 3 3 4 5 3 4 5 6
出力例 3
2 2 3 4 5
这个输入满足小课题1、3、4的否定条件。