HDU 4661 Message Passing ( 树DP + 推公式 )

参考了：

http://www.cnblogs.com/zhsl/archive/2013/08/10/3250755.html

http://blog.csdn.net/chaobaimingtian/article/details/9852761

题意：一个有n个节点的树，每个节点存有一份独一无二的信息，要求用最小的步数，把每个节点的信息共享给所有的节点。一个节点把自己所包含的所有信息传递给相邻的一个节点为一步。

题目不是求最小的步数，而是问最小的步数下，信息传递的方法有多少种。

分析：

最小步数：所有节点把信息传给同一个节点，再由这个节点传给其他节点。因此最小步数为树边数的2倍，即2*(n-1)。我们把这个节点称为信息交换的中心节点。
拓扑排序数：从根节点开始，沿着每个边依次遍历每个点的不同走法。比如对于树：n=4,边为(1,2)(1,3)(2,4)，边的编号依次为1,2,3，设根为1，那么不同的遍历方案有（这里写的是边的序号）：（1,3,2）（1,2,3）（2,1,3）三种。我们说以1为根的拓扑排序数为3。
假设所有节点把信息传给中心节点的拓扑排序数为X，那么再由这个节点传给其他节点的拓扑排序数也为X，总的方法数就是X²。
枚举所有的中心节点X_i, 总方法数即为ans = sum( X_i² ), 1 <= i<= N;
求每个节点的拓扑排序数：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，因为DFS是先根序遍历，因此我们在求以u为中心节点的拓扑排序数dp[u]之前，已经先将以fa为中心节点的拓扑排序数dp[fa]求了出来，因此下面我们可以直接使用这个值。

我们将fa中除去子树u的所有子树合并成一个子树t，根据上面的式子：

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

#include <cstdio>

#include <cstdlib>

#include <cstring>

#define LL long long int

using namespace std;

const int MAXN = ;

const LL MOD = ;

struct Edge

{

    int v;

    int next;

};

int head[MAXN];

Edge D[ MAXN <<  ];

int N, ans;

int EdgeN;

LL cnt[MAXN];

LL dp[MAXN];

LL fac[MAXN];

LL rev[MAXN];

void AddEdge( int u, int v )

{

    D[EdgeN].v = v;

    D[EdgeN].next = head[u];

    head[u] = EdgeN++;

    return;

}

//求逆元模板

void ExGcd( LL a, LL b, LL& d, LL& x, LL& y )

{

    if ( !b ) { d = a, x = , y = ; }

    else

    {

        ExGcd( b, a % b, d, y, x );

        y -= x * ( a / b );

    }

    return;

}

LL GetInverse( LL num )

{

    LL d, x, y;

    ExGcd( num, MOD, d, x, y );

    return ( x % MOD + MOD ) % MOD;

}

//预处理出所有阶乘和逆元

void init()

{

    fac[] = ;

    for ( int i = ; i < MAXN; ++i )

        fac[i] = ( fac[i - ] * i ) % MOD;

    for ( int i = ; i < MAXN; ++i )

        rev[i] = GetInverse( fac[i] );

    return;

}

//第一次DFS，求出以cur为根的子树的节点个数cnt[u]和拓扑排序数dp[cur]

void DFS1( int cur, int fa )

{

    cnt[cur] = dp[cur] = ;

    for ( int i = head[cur]; i != -; i = D[i].next )

    {

        if ( D[i].v == fa ) continue;

        DFS1( D[i].v, cur );

        cnt[cur] += cnt[ D[i].v ];

        dp[cur] = ( (dp[cur]*dp[ D[i].v ])%MOD * rev[cnt[D[i].v]] )%MOD;

    }

    dp[cur] = ( dp[cur] * fac[ cnt[cur]- ] ) % MOD;

    return;

}

//第二次DFS，求出以cur为中心的拓扑排序数dp[cur]

void DFS2( int cur, int fa )

{

    if ( cur !=  )

    {

        dp[cur] = (( (dp[fa]*cnt[cur])%MOD )*GetInverse(N-cnt[cur]))%MOD;

        ans = (ans + dp[cur]*dp[cur]%MOD)%MOD;

    }

    for ( int i = head[cur]; i != -; i = D[i].next )

    {

        if ( D[i].v == fa ) continue;

        DFS2( D[i].v, cur );

    }

    return;

}

int main()

{

    init();

    int T;

    scanf( "%d", &T );

    while ( T-- )

    {

        scanf( "%d", &N );

        EdgeN = ;

        memset( head, -, sizeof(int)*(N+) );

        for ( int i = ; i < N; ++i )

        {

            int u, v;

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

            AddEdge( u, v );

            AddEdge( v, u );

        }

        DFS1( , - );

        ans = dp[] * dp[] % MOD;

        DFS2( , - );

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

    }

    return ;

}

巴特西

HDU 4661 Message Passing ( 树DP + 推公式 )

最新文章

热门文章