← 返回题目列表

AtCoder · typical90_ai

035. 保持连接(★7)

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

配点: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
  • 给定的图是树
  • 所有输入均为整数

小课题·得点

这个问题可以分解为若干小课题,如果所有小课题的测试用例都正确,则被视为“完成了此小课题”。
提交的源码得分为已正确回答的小课题分数之和。

  1. (2 点):N,Q \leq 5000
  2. (1 点):K_j = 2
  3. (1 点):K_j = 3
  4. (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的否定条件。