链接:hdu5647
Description
DZY has an unrooted tree consisting of n nodes labeled from 1 to n.
DZY likes connected sets on the tree. A connected set S is a set of nodes, such that every two nodes u,v in S
- can be connected by a path on the tree, and the path should only contain nodes from
S. Obviously, a set consisting of a single node is also considered a connected set.
The size of a connected set is defined by the number of nodes which it contains. DZY wants to know the sum of
the sizes of all the connected sets. Can you help him count it?
The answer may be large. Please output modulo 109+7.
Input
- First line contains t denoting the number of testcases.t testcases follow. In each testcase, first line
- contains n. In lines 2∼n, ith line contains pi, meaning there is an edge between node i and node pi.
- (1≤pi≤i−1,2≤i≤n) (n≥1, sum of n in all testcases does not exceed 200000)
Output
- Output one line for each testcase, modulo 109+7.
Sample Input
2
1
5
1
2
2
3Sample Output
1
42题解
- ans[i]由两部分组成,这个节点做的贡献dp[u](sum[x]+1) 孩子做的贡献dp[x]sum[u]
- 具体看代码
1 |
|