#P12698. [KOI 2022 Round 2] 树与查询
[KOI 2022 Round 2] 树与查询
题目背景
试题来源:https://koi.or.kr/archives/。中文翻译做了少量本土化修改。
按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。
题目描述
有一个由 1 到 的 个节点组成的树。第 条边连接两个不同的节点 和 。()
在这 个节点中选择一些节点,记为 。如果存在 (),使得 ,则称节点 属于集合 。
如果集合 中的两个不同节点 和 满足,仅通过集合 中的节点即可在树上从 移动到 ,则称“ 和 在 上是连接的”。
例如,考虑如下树()。如果 且 ,则 “1 和 2”、“3 和 5”、“4 和 6”在集合 上是连接的。
然而,“1 和 6”、“2 和 7”在集合 上不是连接的。
我们定义满足以下条件的节点对 的数量为集合 的连接强度:
- 和 是不同的两个节点。
- 。
- 和 在集合 上是连接的。
给定一个选择的节点集合 ,请计算 的连接强度。你需要回答 个查询。
输入格式
第一行给出整数 。
接下来 行,每行包含两个整数 和 ,表示第 条边连接的两个节点。
接着是一个整数 ,表示查询的数量。
接下来 行,每行表示一个查询。每个查询首先给出整数 ,接着是 个整数 ,表示集合 。
输出格式
对于每个查询,输出一行,表示该查询中给定集合 的连接强度。
7
1 2
1 3
1 5
2 7
4 6
4 7
6
1 1
2 1 2
4 1 2 3 4
5 1 2 4 6 7
6 1 2 3 4 5 6
7 1 2 3 4 5 6 7
0
1
3
10
7
21
提示
约束条件
- 对于所有的 (),有 。
- 对于所有的 (),有 。
- 对于所有的 (),有 。
- 给定的图是树。
- 对于每个查询,。
- 对于每个查询,给出的 K 个节点 是不同的。
- 在 个查询中,所有的 总和不超过 1,000,000。
子任务
- (3 分)。
- (10 分)。
- (11 分)。
- (13 分)每个查询中,。
- (63 分)无额外约束条件。