题意：
给一棵树，每一个结点都有一个信息，每一个时刻，某一对相邻的结点之间可以传递信息，那么存在一个最少的时间，使得所有的节点都可以拥有所有的信息。但是，题目不是求最短时间，而是求最短时间的情况下，有多少种传递方式：某一时刻传递信息的双方不一样则认为是不同的传递方式。
容易的出，最短的时间内，当然是每个节点将自己的信息想外传出去一次，并且接受一次信息，也就是树边的2倍【2*（n-1）】。
然后可以证明，在最短时间内，所有的传递方式都有一个“信息转换点”——其他节点的信息首先传递到此节点，然后信息再从这个节点向其他节点传递。
那么总方案数的计算就是可以枚举每个节点，将这个节点作为根节点，然后求当前情况下的方案——先求以当前节点为根的拓扑排序数，然后平方就是当前方案数。
拓扑排序数的计算方法：
c[i] 表示以i为根的子树的节结点（包含结点 i）
f[i] 表示以i为根的子树的拓扑排序数
则：当前结点now的拓扑排序数：
f[now] = f[son1]*f[son2]....f[sonx] * (c[now] - 1)! / (c[son1]! * c[son2]! * ... c[sonx]!)
即：所有子结点的排列数除以每颗子树所有结点的排列数（去重，对于子树的每一种拓扑序），然后乘以所有子树的拓扑序总数。
一遍dfs之后，就可以求出根节点的f值，然后在一边dfs，就可以依次求出所有节点的f值。
转移方法：
根据父节点的f值计算出去掉当前now节点之后的f值，然后以now为根节点，重新计算即可。看代码实现了。
这里用到了逆元，整个程序的速度有点慢。求逆元可以用扩展欧几里得算法，这里用的是费马定理，快速幂：x^(P-2)%P 就是x的逆元。
还有就是树dp，要避免用递归，但是还是用了，会爆栈的，所以就用手工栈了。
手工栈的方法：http://blog.csdn.net/yang_7_46/article/details/9853061
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4661
//#pragma comment(linker, "/STACK:102400000,102400000")//c++ #include<cstdio> #include<iostream> #include<cstdlib> #include<algorithm> #include<cmath> #include<string> #include<cstring> #include<set> #include<map> #include<list> #include<queue> #include<vector> #define tree int o,int l,int r #define lson o<<1,l,mid #define rson o<<1|1,mid+1,r #define lo o<<1 #define ro o<<1|1 #define ULL unsigned long long #define LL long long #define UI unsigned int #define inf 0x7fffffff #define eps 1e-7 #define M 1000000007 #define N 1000009 using namespace std; int T,n,m,k,t,maxv; vector<int>g[N]; LL f[N],c[N]; LL ep[N],res; void init() { for (int i=0; i<=n; ++i) g[i].clear(); } //LL powermod(LL a,LL k,LL p)//逆元！（a关于p的） //{ // LL ans=1; // while(k) // { // if(k&1) // ans=ans*a%M; // a=a*a%M; // k>>=1; // } // return ans; //} void gcd(LL a,LL b,LL&d,LL &x,LL &y) { if(!b) { d=a,x=1,y=0; } else { gcd(b,a%b,d,y,x); y-=x*(a/b); } } LL inv(LL a,LL n) { LL d,x,y; gcd(a,n,d,x,y); return d==1?(x+n)%n:-1; } void dfs(int u,int fa) { LL cc=1,ff=1; c[u]=1; for(int i=0; i<g[u].size(); i++) { int v=g[u][i]; if(v!=fa) { dfs(v,u); c[u]+=c[v]; ff=ff*f[v]%M; cc=cc*ep[c[v]]%M; } } // cc=powermod(cc,M-2,M); cc=inv(cc,M); f[u]=(ep[c[u]-1]*ff%M)*cc%M; } void dfs1(int u,int fa) { if(u!=1) { LL t=((ep[c[u]-1])*(n-c[u])%M)*f[u]%M; // t=powermod(t,M-2,M); t=inv(t,M); f[u]=((f[u]*f[fa]%M)*ep[c[u]]%M)*t%M; res=(res+f[u]*f[u]%M)%M; } for(int i=0; i<g[u].size(); i++) { int v=g[u][i]; if(v!=fa) { dfs1(v,u); } } } int main() { #ifndef ONLINE_JUDGE freopen("ex.in","r",stdin); #endif int size = 256 << 20; // 256MB char *p = (char*)malloc(size) + size; __asm__("movl %0, %%esp " :: "r"(p));//g++扩栈 int ncase=0; ep[0]=1; for(int i=1; i<N; i++) ep[i]=ep[i-1]*i%M; scanf("%d",&T); while(T--) { scanf("%d",&n); init(); for(int i=1; i<n; i++) { int x,y; scanf("%d%d",&x,&y); g[x].push_back(y); g[y].push_back(x); } dfs(1,-1); res=f[1]*f[1]%M; dfs1(1,-1); printf("%I64d ",res); } return 0; }