砍树

题目描述

奶龙在一片神奇的森林里发现了一棵巨大的树，这棵树有 $n$ 个节点，节点编号为 $1$ 到 $n$。奶龙对这棵树非常感兴趣，决定进行一些探索。他会给你 $q$ 个询问，每个询问他会砍掉一个集合 $S$ 的所有节点，请你计算剩余连通块的大小的平方和。注意，移除后的剩余部分可能形成多个连通块，每个连通块的大小为其包含的节点数目。

输入格式

第一行输入一个整数 $n$（$2 \leq n \leq 10^6$），表示树的节点数。
接下来 $n-1$ 行，每行两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$），表示树中的一条边。
接下来一行输入一个整数 $q$（$1 \leq q \leq 10^5$），表示询问的次数。
接下来 $q$ 组询问，每组询问的格式如下：

• 第一个整数 $k$（$1 \leq k \leq n$），表示集合 $S$ 的大小。
• 接下来 $k$ 个不同的整数 $s_1, s_2, \ldots, s_k$（$1 \leq s_i \leq n$），表示要移除的节点。

保证所有询问中 $k$ 的总和不超过 $10^6$。

输出格式

输出共 $q$ 行，每行一个整数，对应每个询问的结果。

样例输入

5
1 2
2 3
3 4
3 5
2
1 3
2 2 5

样例输出

6
5

提示

样例解释：

• 第一个询问移除节点 $3$，剩余连通块为 $\{1,2\}$、$\{4\}$、$\{5\}$，平方和为 $2^2 + 1^2 + 1^2 = 6$。
• 第二个询问移除节点 $2$ 和 $5$，剩余连通块为 $\{1\}$、$\{3,4\}$，平方和为 $1^2 + 2^2 = 5$。

数据范围：

• 40% 数据：$n \leq 1000$，$q \leq 1000$，且所有 $k$ 的总和不超过 $10^4$。
• 100% 数据：$n \leq 10^6$，$q \leq 10^6$，所有 $k$ 的总和不超过 $10^6$。