#P18924. [2026多校联测]树与查询

[2026多校联测]树与查询

树与查询

A. 树与查询

题目描述

给定一棵含有 NN 个节点的树,节点编号为 11 到 NN。第 ii 条边连接两个不同的节点 AiA_i 和 BiB_i(1≤i≤N−11\le i\le N-1)。

设 S={s1,…,sK}S=\{s_1,\ldots,s_K\}。当且仅当存在某个 ii 使得 si=vs_i=v 时,称节点 vv 属于 SS。

对于两个不同的节点 u,vu,v,如果可以仅经过 SS 中的节点从 uu 移动到 vv,则称 u,vu,v 在 SS 上连通。

例如,N=7N=7,K=6K=6,S={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) 的数量:u≠vu\ne v,1≤u<v≤N1\le u<v\le N,且 u,vu,v 在 SS 上连通。

给定 SS,请计算其连通强度。需要回答 QQ 次询问。

输入格式

第一行包含一个整数 NN。

接下来 N−1N-1 行,每行包含两个整数 Ai,BiA_i,B_i,表示一条边。

接下来一行包含一个整数 QQ。

接下来 QQ 行描述询问。每行先给出整数 KK,随后给出 KK 个整数 s1,…,sKs_1,\ldots,s_K。

输出格式

对于每个询问,输出一行一个整数,表示连通强度。

样例

输入:

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

数据范围与子任务

  • 2≤N≤2500002\le N\le 250000;1≤Q≤1000001\le Q\le 100000。
  • 对于所有 ii,1≤Ai,Bi≤N1\le A_i,B_i\le N 且 Ai≠BiA_i\ne B_i;给定图是一棵树。
  • 对于每个询问,1≤K≤N1\le K\le N,且 KK 个节点互不相同。
  • 所有询问的 KK 之和不超过 10000001000000。
子任务 分值 限制
1 3 N=3N=3
2 10 N≤50, Q≤50N\le 50,\ Q\le 50
3 11 N≤2500, Q≤2500N\le 2500,\ Q\le 2500
4 13 每次询问 K=3K=3
5 63 无额外限制