#P12698. [KOI 2022 Round 2] 树与查询

[KOI 2022 Round 2] 树与查询

题目背景

试题来源:https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

有一个由 1 到 NNNN 个节点组成的树。第 ii 条边连接两个不同的节点 AiA_iBiB_i。(1iN11 \leq i \leq N - 1

在这 NN 个节点中选择一些节点,记为 S={s1,s2,,sK}S = \{s_1, s_2, \dots, s_K\}。如果存在 ii1iK1 \leq i \leq K),使得 si=vs_i = v,则称节点 vv 属于集合 SS

如果集合 SS 中的两个不同节点 uuvv 满足,仅通过集合 SS 中的节点即可在树上从 uu 移动到 vv,则称“uuvvSS 上是连接的”。

例如,考虑如下树(N=7N = 7)。如果 K=6K = 6S={1,2,3,4,5,6}S = \{1, 2, 3, 4, 5, 6\},则 “1 和 2”、“3 和 5”、“4 和 6”在集合 SS 上是连接的。

然而,“1 和 6”、“2 和 7”在集合 SS 上不是连接的。

我们定义满足以下条件的节点对 (u,v)(u, v) 的数量为集合 SS 的连接强度:

  1. uuvv 是不同的两个节点。
  2. 1u<vN1 \leq u < v \leq N
  3. uuvv 在集合 SS 上是连接的。

给定一个选择的节点集合 SS,请计算 SS 的连接强度。你需要回答 QQ 个查询。

输入格式

第一行给出整数 NN

接下来 N1N - 1 行,每行包含两个整数 AiA_iBiB_i,表示第 ii 条边连接的两个节点。

接着是一个整数 QQ,表示查询的数量。

接下来 QQ 行,每行表示一个查询。每个查询首先给出整数 KK,接着是 KK 个整数 s1,s2,,sKs_1, s_2, \dots, s_K,表示集合 SS

输出格式

对于每个查询,输出一行,表示该查询中给定集合 SS 的连接强度。

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

提示

约束条件

  • 2N250,0002 \leq N \leq 250,000
  • 1Q100,0001 \leq Q \leq 100,000
  • 对于所有的 ii1iN11 \leq i \leq N - 1),有 1AiN1 \leq A_i \leq N
  • 对于所有的 ii1iN11 \leq i \leq N - 1),有 1BiN1 \leq B_i \leq N
  • 对于所有的 ii1iN11 \leq i \leq N - 1),有 AiBiA_i \neq B_i
  • 给定的图是树。
  • 对于每个查询,1KN1 \leq K \leq N
  • 对于每个查询,给出的 K 个节点 s1,s2,,sKs_1, s_2, \dots, s_K 是不同的。
  • QQ 个查询中,所有的 KK 总和不超过 1,000,000。

子任务

  1. (3 分)N=3N = 3
  2. (10 分)N50,Q50N \leq 50, Q \leq 50
  3. (11 分)N2,500,Q2,500N \leq 2,500, Q \leq 2,500
  4. (13 分)每个查询中,K=3K = 3
  5. (63 分)无额外约束条件。