2

2

1 2

3

1 2

2 3

2

6

field=problem&key=2013+Multi-University+Training+Contest+6&source=1&searchmode=source">2013 Multi-University Training Contest 6

pid=5016" target="_blank">5016 5015 

pid=5014" target="_blank">5014 5013 

每次共享为一次操作。问每一个人都拥有全部人的信息最小要的次数的共享方法有多少种。

事实上我们要求的就是拓扑序有多少种。定义dp[u]表示u节点下面。传到u节点的拓扑序有多少种，cnt[u]表示u有多少个子孙节点，f[i] = i!(i的阶乘)。c[i][j]表示组合数。

如果它有v1,v2,v3个节点。它们的拓扑序分别有dp[v1],dp[v2],dp[v3]这么多种。

那么dp[u] = c[cnt[u]-1][cnt[v1]] * c[cnt[u]-1-cnt[v1]][cnt[v2]]
* c[cnt[u]-1-cnt[v1]-cnt[v2]][cnt[v3]] * dp[v1] * dp[v2] * dp[v3]（这个自己推推吧）。化简以后。得到dp[u] = f[cnt[u]-1] / ( f[cnt[v1]] * f[cnt[v2]] * f[cnt[v3]] ) * dp[v1] * dp[v2] * dp[v3] 。我们能够在o（n）的时间复杂度内算出以1节点为根的全部dp值（那么以1为根的答案就算出来了）。以及其它一些辅助信息的值。然后按树的结构往下遍历。分别计算以其它节点为根的答案。以上是网上的思路。我想说的是自己的一点理解。为什么知道每一个子树的拓扑序数目。就能够退出自己的拓扑序数目呢。事实上非常好理解的。当每一个子树的拓扑序定下来之后。确定总顺序的时候。

也就是要得到一个长度为cnt[u]拓扑序列。

对于子树i。

也有一个长度为cnt[i]拓扑序列，所以就要在cnt[u]里找cnt[i]个位置。其它子树再在剩下的子树里找。

还有换根的时候该怎么推导。先写出

由于信息传回去的时候就是你拓扑序嘛。和拓扑序数目一样的。

每个正拓扑序能够和一个逆拓扑序组合。所以就有平方种啦。

#include<algorithm>

#include<iostream>

#include<string.h>

#include<stdio.h>

using namespace std;

const int INF=0x3f3f3f3f;

const int maxn=1000010;

#pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long ll;

const ll mod=1e9+7;

ll fac[maxn],dp[maxn],ans;

int cnt,sz[maxn],n;

struct node

{

    int v;

    node *next;

} ed[maxn<<1],*head[maxn];

void adde(int u,int v)

{

    ed[cnt].v=v;

    ed[cnt].next=head[u];

    head[u]=&ed[cnt++];

}

ll pow_mod(ll x,int k)

{

    ll base=x,ret=1;

    while(k)

    {

        if(k&1)

            ret=(ret*base)%mod;

        base=(base*base)%mod;

        k>>=1;

    }

    return ret;

}

ll ni(ll x){    return pow_mod(x,mod-2);    }

void dfs(int fa,int u)

{

    ll tp;

    dp[u]=tp=sz[u]=1;

    for(node *p=head[u];p!=NULL;p=p->next)

    {

        int v=p->v;

        if(v==fa)

            continue;

        dfs(u,v);

        tp=(tp*ni(fac[sz[v]]))%mod;

        dp[u]=(dp[u]*dp[v])%mod;

        sz[u]+=sz[v];

    }

    dp[u]=(dp[u]*fac[sz[u]-1]%mod*tp)%mod;

}

void solve(int fa,int u,ll tp)

{

    ll tt;

    ans=(ans+tp*tp%mod)%mod;

    for(node *p=head[u];p!=NULL;p=p->next)

    {

        int v=p->v;

        if(v==fa)

            continue;

        tt=(tp*fac[n-sz[v]-1]%mod*fac[sz[v]])%mod;

        tt=(tt*ni(fac[sz[v]-1])%mod*ni(fac[n-sz[v]]))%mod;

        solve(u,v,tt);

    }

}

int main()

{

    int t,i,u,v,rt;

    fac[0]=fac[1]=1;

    for(i=2;i<maxn;i++)

        fac[i]=(i*fac[i-1])%mod;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        cnt=0,ans=0;

        for(i=1;i<=n;i++)

            head[i]=NULL;

        for(i=1;i<n;i++)

        {

            scanf("%d%d",&u,&v);

            adde(u,v);

            adde(v,u);

        }

        rt=(n+1)/2;

        dfs(-1,rt);

        solve(-1,rt,dp[rt]);

        printf("%I64d\n",ans);

    }

    return 0;

}

版权声明：本文博主原创文章，博客，未经同意不得转载。