Message Passing
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1184 Accepted Submission(s): 420
Problem Description There are n people numbered from 1 to n. Each people have a unique message. Some pairs of people can send messages directly to each other, and this relationship forms a structure of a tree. In one turn, exactly one person sends all messages s/he currently has to another person. What is the minimum number of turns needed so that everyone has all the messages?
This is not your task. Your task is: count the number of ways that minimizes the number of turns. Two ways are different if there exists some k such that in the k-th turn, the sender or receiver is different in the two ways.
Input First line, number of test cases, T.
Following are T test cases.
For each test case, the first line is number of people, n. Following are n-1 lines. Each line contains two numbers.
Sum of all n <= 1000000.
Output T lines, each line is answer to the corresponding test case. Since the answers may be very large, you should output them modulo 10
9+7.
Sample Input
2
2
1 2
3
1 2
2 3
Sample Output
2
6
Source 2013 Multi-University Training Contest 6
思路来源于：点击打开链接
题意： 一个有n个节点的树，每个节点存有一份独一无二的信息，要求用最小的步数，把每个节点的信息共享给所有的节点，问最小步数的方案有多少种。
思路： 通过分析能知最小步数为边的两倍2*（n-1），方案为先将所有信息汇集到一个点，然后再从这个点发散到所有边，这样的策略是最优的。比如先汇集到u点的方案数，那么就是以u点为根的树的拓扑排序数，现在问题变为求树上每个点的拓扑排序数，用树形dp解决。 DFS一次，记录dp[u], cnt[u]。dp[u]为以u为根节点的子树的拓扑排序数，cnt[u]为以u为根节点的子树的节点的个数。假设v1，v2为u的两个子树，那么v1, v2合并后的拓扑排序数为：sum = dp[v1]*dp[v2]*C( cnt[v1]+cnt[v2], cnt[v1]);（C为组合数公式）对于u的所有儿子，可以采用两两合并的方法。这样可以得到根的拓扑排序数。
求以u为中心节点的拓扑排序数dp[u]（即u为整棵树的根节点）：再次DFS一遍。
设u的父亲为fa，t为fa除去u子树的树，那么有 dp[fa]=dp[t]*dp[u]*C(n-1,num[u]);
将u看做跟时，合并t子树和原来的子树，有 dp1[u]=dp[u]*dp[t]*C(n-1,num[u]-1); 联立两个式子，有dp1[u]=dp[fa]*num[u]/(n-num[u]); 答案即为∑dp[u]^2.
代码：
#include
#include
#include
#include
#include
#include
#include