今天多校的比賽題，在比賽最後2分鐘AC了。。。太無語and驚險了！感覺被描述不清的題意坑了~
題意：
給你一顆樹，每個節點都有各自獨一無二的資訊，每一次你可以把某個節點已有的所有資訊傳遞給其相鄰的另一個節點，最少需要多少次傳遞使得所有節點都有其他節點的所有資訊？
不過。。這不是我們要解決的問題。。。現在要解決的是滿足最少傳遞次數的所有的情況有多少種，結果對10^9+7取餘。 ps：兩種不同的情況為至少存在一個k，使得第k次傳遞資訊接受方或者發送方不同。
坑爹的是我在比賽最後三分鐘交了一發，- -居然爆棧了，還是很淡定地手動加個棧交了，居然wrong answer了。。。這下無語了，還剩兩分鐘，這該怎麼檢查錯誤= =。。随便掃了一下代碼，突然想到剛開始我對于n = 1的情況特判了下，直接輸出0了，因為我認為既然隻有一個人，那他就已經有所有的資訊了，就不需要傳遞了。。。但這種時候還是順便改成1又交了一發，其實根本沒
抱多少希望，居然AC了！！！這真是又雷又驚喜。。。
解題思路：
首先可以很容易得出最少傳遞次數為邊數的兩倍，這個不懂的自己在紙上畫個圖就清楚了。、
我們要使得所有資訊傳到所有節點，其實就是需要一個中介點，把這個店看成根節點，首先其所有子樹把資訊傳上來，這樣這個點就有了所有的資訊了，然後把資訊傳回各個子樹，這樣所有點都會有所有的資訊了。也就是說中介點可能會是任意一個點，那麼我們就是要求出所有點為中介點的情況總數。
把問題先簡化一下，我們令1為根節點，要求出所有子樹把資訊傳到根節點的情況數，對于每一個子樹内部傳遞順序都是不受影響的，但是每個子樹相對間的順序是不一樣的，這個就是組合數學了。用cnt[i]表示i節點所有子樹的節點數，mul[i]表示該節點子樹的資訊彙聚到該節點的所有情況數，對于每一個節點都是把該節點所有子樹的情況組合起來，mul[u] = mul[son1]*mul[son2]*...* C(cnt[u] , cnt[son1]+1) * C(cnt[u] - cnt[son1]-1 , cnt[son2]+1) *...
注意求組合數要用到除法取模，這裡我直接用了擴充歐幾裡得來求逆，也可以利用費馬小定理來解。
這樣子隻求出了以1為中介點的的情況數，其他節點儲存的mul[u]隻是表示其節點所有子樹資訊彙聚到該節點的情況數，而該節點父親這邊的資訊還沒有傳過來，是以還要進行一次dfs進行轉移，這個具體怎麼轉移大家可以好好想想。實在不懂的可以參考下我的代碼。。。雖然寫的有點搓，比賽最後時候有點急了。。。
ps：由于本人表達能力太差。。。寫解題報告也是想為了提高表達能力，寫的太爛希望大家别介意。。有什麼不清楚的可以直接問我。。
code：
#pragma comment(linker,"/STACK:100000000,100000000")
#include <stdio.h>
#define LL __int64
const int mod = 1000000007;
const int maxn = 1000003;
struct EDGE{
int to, next;
}edge[maxn*2];
int head[maxn], E, cnt[maxn];
LL jie[maxn], mul[maxn];
void init(int n) {
for(int i = 1;i <= n; i++) head[i] = -1;
E = 0;
}
void newedge(int u, int to) {
edge[E].to = to;
edge[E].next = head[u];
head[u] = E++;
}
LL modstyle(LL x) { // 取餘操作，由于取餘%很慢的，這樣寫效率比較好
if(x >= mod) x %= mod;
else if(x < 0) {
x = (x%mod+mod)%mod;
}
return x;
}
// 擴充歐幾裡得 求逆元
LL exgcd(LL a ,LL b, LL &x, LL &y) {
if(b == 0) {
x = 1; y = 0;
return a;;
}
LL ans = exgcd(b, a%b, y, x);
y = y - a/b*x;
return ans;
}
// 求組合數 Ｃ（ｎ，ｋ）
LL cal(int n, int k) {
LL x, y;
LL d = exgcd(jie[n-k]*jie[k], mod, x, y);
x = modstyle(x);
return jie[n]*x%mod;
}
// 第一次DFS統計出每個節點的所有的子樹的總結點數cnt[u]，子樹節點資訊傳到該節點的情況數mul[u]
void dfs1(int u, int pre) {
cnt[u] = 0;
mul[u] = 1;
for(int i = head[u];i != -1;i = edge[i].next) {
int to = edge[i].to;
if(to != pre) {
dfs1(to, u);
cnt[u] += cnt[to]+1;
mul[u] = modstyle(mul[u]*mul[to]);
}
}
int sum = cnt[u];
for(int i = head[u];i != -1;i = edge[i].next) {
int to = edge[i].to;
if(to != pre) {
mul[u] = modstyle(mul[u]*cal(sum, cnt[to]+1)); // 對于子樹的情況利用組合數進行彙聚
sum -= cnt[to]+1;
}
}
}
LL ans = 0;
int n;
void dfs2(int u, int pre) {
if(pre != -1) { // 父節點的資訊傳到該節點進行更新計算
LL x, y;
LL d = exgcd(cal(n-1, cnt[u]+1), mod, x, y);
x = modstyle(x);
LL cur = mul[pre]*x%mod;
cur = cur*cal(n-1, cnt[u])%mod;
mul[u] = cur;
ans = (ans + cur*cur)%mod;
}
for(int i = head[u];i != -1;i = edge[i].next) {
int to = edge[i].to;
if(to != pre) {
dfs2(to, u);
}
}
}
int main() {
int i, t, u, to;
jie[0] = 1;
for(i = 1;i <= 1000000; i++) {
jie[i] = modstyle(jie[i-1]*i);
}
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
if(n == 1) {
puts("1");
continue;
}
init(n);
for(i = 0;i < n-1; i++) {
scanf("%d%d", &u, &to);
newedge(u, to);
newedge(to, u);
}
dfs1(1, -1);
ans = mul[1]*mul[1]%mod;
dfs2(1, -1);
printf("%I64d\n", ans);
}
return 0;
}