树与查询
A. 树与查询
题目描述
给定一棵含有 N 个节点的树,节点编号为 1 到 N。第 i 条边连接两个不同的节点 Ai 和 Bi(1≤i≤N−1)。
设 S={s1,…,sK}。当且仅当存在某个 i 使得 si=v 时,称节点 v 属于 S。
对于两个不同的节点 u,v,如果可以仅经过 S 中的节点从 u 移动到 v,则称 u,v 在 S 上连通。
例如,N=7,K=6,S={1,2,3,4,5,6} 时,节点对“1 和 2”、“3 和 5”、“4 和 6”在 S 上连通,而“1 和 6”、“2 和 7”不连通。

定义 S 的连通强度为满足以下条件的节点对 (u,v) 的数量:u=v,1≤u<v≤N,且 u,v 在 S 上连通。
给定 S,请计算其连通强度。需要回答 Q 次询问。
输入格式
第一行包含一个整数 N。
接下来 N−1 行,每行包含两个整数 Ai,Bi,表示一条边。
接下来一行包含一个整数 Q。
接下来 Q 行描述询问。每行先给出整数 K,随后给出 K 个整数 s1,…,sK。
输出格式
对于每个询问,输出一行一个整数,表示连通强度。
样例
输入:
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≤250000;1≤Q≤100000。
- 对于所有 i,1≤Ai,Bi≤N 且 Ai=Bi;给定图是一棵树。
- 对于每个询问,1≤K≤N,且 K 个节点互不相同。
- 所有询问的 K 之和不超过 1000000。
| 子任务 |
分值 |
限制 |
| 1 |
3 |
N=3 |
| 2 |
10 |
N≤50, Q≤50 |
| 3 |
11 |
N≤2500, Q≤2500 |
| 4 |
13 |
每次询问 K=3 |
| 5 |
63 |
无额外限制 |