시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 8 | 4 | 4 | 50.000% |
Chiaki has a tree with $n$ vertices, labeled by integers from $1$ to $n$. For each vertex in the tree, there is a white token or a black token or no token at all. There are exactly $w$ white tokens and exactly $b$ black tokens. Also, for each pair of vertices with the same color of tokens, there exists a path between them such that every vertex on the path contains a token of the same color.
Chiaki would like to perform the following operations:
For two initial configurations of tokens $S$ and $T$, if Chiaki could perform the above operations several (zero or more) times to make $S$ become $T$, then $S$ and $T$ are considered equivalent.
Let $f(w, b)$ be the number of equivalence classes (that is, the maximum number of configurations that no two are equivalent). Chiaki would like to know the value of
$$\left(\sum\limits_{w=1}^{n-1}\sum\limits_{b=1}^{n-w} w \cdot b \cdot f(w, b) \right)\bmod (10^9+7)\text{.}$$
There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:
The first line contains an integer $n$ ($2 \le n \le 2 \cdot 10^5$): the number of vertices in the tree.
The second line contains $n-1$ integers $p_2,p_3,\ldots,p_n$ ($1 \le p_i < i$), where $p_i$ means there is an edge between vertex $i$ and vertex $p_i$.
It is guaranteed that the sum of $n$ of all test cases will not exceed $2 \cdot 10^5$.
For each test case, output an integer denoting the value of
$$\left(\sum\limits_{w=1}^{n-1}\sum\limits_{b=1}^{n-w} w \cdot b \cdot f(w, b) \right)\bmod (10^9+7)\text{.}$$
2 5 1 2 3 3 10 1 2 3 4 3 6 3 8 2
71 989
For the first sample, the values of $f(w,b)$ for each $w$ and $b$ are: \\ $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$.