HDU 4661 Message Passing (樹形DP+組合數學知識+拓撲排序計數思維)*

Message Passing

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Total Submission(s): 1461    Accepted Submission(s): 541

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 109+7.

Sample Input

2 2 1 2 3 1 2 2 3

Sample Output

2 6

Source

2013 Multi-University Training Contest 6

Recommend

zhuyuanchen520   |   We have carefully selected several similar problems for you:  6447 6446 6445 6444 6443 

#pragma comment(linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
using namespace std;

#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)

#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define ll long long

const int  maxn =1e6+5;
const int mod=1e9+7;
/*
題目大意:資訊傳送問題，
一個人傳給另一個人是代表着把他所有資訊都發送出去。
求所有人都有資訊的方法數。

這題好難，對于現在的我來說感覺比賽時遇到都吃力，
頂多算是漲漲見識吧。。。。

分析一波，首先最優的 方法便是所有人把資訊彙總到一個人（拓撲排序）
然後那個人再彙總回去，隻考慮單向的即可，最終的答案是平方的sigma 。

拓撲排序的方案數有多少呢?或者說對于一個點來說，傳給他的方法數有多少呢.
dp[u]=(乘積) dp[vi]*(n-1)!/(cnti!),在組合數學中可以看成分塊計數，
就是說cnt個數，共有n-1個，每個數代表個方案數（表達淩亂。。。）
簡單說就是先分塊，然後每個塊都有dp[vi]方案數，乘積即可。

可以簡單的用樹形DP求出關于子樹的答案貢獻，
如何加上父節點的影響呢? 二次DFS。

因為DFS是根節點優先的，是以可以假定dp[u]已經計算好了，
具體公式我不會打，可以參考大佬的部落格
https://www.cnblogs.com/GBRgbr/p/3312866.html
總之最後的推到式是：
dp2[u]=dp[fa]*cnt[u]/(n-cnt[u])。
第二次DFS推一下即可。
*/

ll powmod(ll x,ll y) { ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}

int n,x,y;
///鍊式前向星
struct node{int u,nxt;};
int head[maxn],tot=0;
node edge[maxn<<1];
void init() {memset(head,-1,sizeof(head));tot=0;}
void add(int x,int y){edge[tot]=node{y,head[x]};head[x]=tot++;}
///擴充歐幾裡得求逆元
void Exgcd(ll a,ll b,ll &d,ll &x,ll &y)
{
    if(b==0)
    {
        x=1,y=0,d=a;
        return ;
    }
    else
    {
        Exgcd(b,a%b,d,y,x);
        y-=x*(a/b);
    }
    return ;
}
ll Get_inv(ll a)
{
    ll d,x,y;
    Exgcd(a,mod,d,x,y);
    return (x%mod+mod)%mod;
}
///組合數和逆元預處理
ll fac[maxn],inv[maxn];
void get_inv()
{
    fac[0]=1;for(int i=1;i<maxn;i++) fac[i]=fac[i-1]*i%mod;
    inv[maxn-1]=powmod(fac[maxn-1],mod-2);
    for(int i=maxn-2;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
ll C(ll n,ll m) { return 1LL*fac[n]*inv[m]%mod*inv[n-m]%mod; }
///用DFS進行拓撲計數
ll cnt[maxn],dp[maxn];
ll ans=0;
void dfs1(int u,int pre)
{
    dp[u]=cnt[u]=1;
    for(int i=head[u];~i;i=edge[i].nxt)
    {
        int v=edge[i].u;
        if(v==pre) continue;
        dfs1(v,u);
        dp[u]=dp[u]*dp[v]%mod*inv[cnt[v]]%mod;
        cnt[u]+=cnt[v];
    }
    dp[u]=dp[u]*fac[cnt[u]-1]%mod;
    return ;
}

void dfs2(int u,int pre)
{
    if(u!=1)
    {

        dp[u]=dp[pre]*cnt[u]%mod*Get_inv(n-cnt[u])%mod;
        ans=(ans+dp[u]*dp[u]%mod)%mod;
    }
    for(int i=head[u];~i;i=edge[i].nxt)
    {
        int v=edge[i].u;
        if(v==pre) continue;
        dfs2(v,u);
    }
    return ;
}

int main()
{
    int t;scanf("%d",&t);
    get_inv();
    while(t--)
    {
        init();  scanf("%d",&n);

        memset(dp,0,sizeof(dp));
        memset(cnt,0,sizeof(cnt));

        for(int i=0;i<n-1;i++)
        {
            scanf("%d%d",&x,&y);
            add(x,y),add(y,x);
        }

        ans=0;
        dfs1(1,-1);
        ans=dp[1]*dp[1]%mod;
        dfs2(1,-1);
        printf("%lld\n",ans);
    }
    return 0;
}