有一棵 $n$ 个点的树,顶点的编号为 $1$ 到 $n$。
对于树中的每个顶点,可能存在一个白色的棋子、一个黑色的棋子,或者没有棋子。树上正好有 $w$ 个白色棋子和 $b$ 个黑色棋子。另外,对于每一对具有相同颜色棋子的顶点,存在一条路径,路径上的每个顶点都包含相同颜色的棋子(即每种颜色的棋子形成一个连通块)。
你可以进行任意次以下操作:
- 选择一个带有棋子的顶点 $u$。
- 选择一条路径 $p_1, p_2, \dots, p_k$,使得 $p_1 = u$,且所有顶点 $p_1, p_2, \dots, p_{k-1}$ 都包含相同颜色的棋子,且 $p_k$ 上没有棋子。
- 将 $p_1$ 上的棋子移动到 $p_k$。此时 $p_1$ 上没有棋子,$p_k$ 上有一个棋子。
在每一步操作后,每种颜色的棋子仍然形成一个连通块。
对于两个初始的棋子状态 $S$ 和 $T$,如果你可以通过上述操作若干次(可以为零次)将 $S$ 变为 $T$,那么我们认为 $S$ 和 $T$ 是等价的。
定义 $f(w, b)$ 为在树上有 $w$ 个白色棋子和 $b$ 个黑色棋子时,等价类的数量。你需要求出:
$$(\sum_{w=1}^{n-1}\sum_{b=1}^{n-w} f(w,b)· w· b)\bmod 10^9+7$$
输入格式
第一行包含一个整数 $T$,表示数据组数。
对于每组数据:
第一行一个数 $n$,表示树的大小。
第二行对于 $i=2\sim n$,输入 $n-1$ 个数 $fa_i (1\le fa_i < i)$,表示树上有边 $(fa_i,i)$。
输出格式
对于每组数据输出一行一个数,表示答案。
输入输出样例
样例输入 1
2 5 1 2 3 3 10 1 2 3 4 3 6 3 8 2
样例输出 1
71 989
样例输入输出 2,3,4,5,6,7
见下发文件。
样例解释
对于第一个样例:
- $f(1, 1) = 1, f(1, 2) = 2, f(1, 3) = 3, f(1, 4) = 3,$
- $f(2, 1) = 2, f(2, 2) = 2, f(2, 3) = 1,$
- $f(3, 1) = 3, f(3, 2) = 1,$
- $f(4, 1) = 3.$
数据范围
对于所有数据:$n \ge 2,1\le \sum n\le 2\times 10^5,1\le fa_i < i$。
子任务编号 | $\sum n\le $ | 特殊性质 | 分值 |
---|---|---|---|
$1$ | $10$ | 无 | $12$ |
$2$ | $2\times 10^5$ | $fa_i = 1$ | $8$ |
$3$ | $2\times 10^5$ | $n=2^k-1,fa_i = \lfloor \frac{i}{2} \rfloor$ | $15$ |
$4$ | $2\times 10^5$ | 存在正整数 $k,m$ 使得 $n=mk+1,fa_i = \max(1,i-k)$ | $15$ |
$5$ | $500$ | 无 | $10$ |
$6$ | $3000$ | 无 | $15$ |
$7$ | $2\times 10^5$ | 无 | $25$ |