Public Judge

pjudge

Time Limit: 1 s Memory Limit: 2048 MB Total points: 100 Hackable ✓
Statistics

有一棵 $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$