首页 > 代码库 > hdu 4661 Message Passing （思维 dp求拓扑排序数）

hdu 4661 Message Passing （思维 dp求拓扑排序数）

2024-07-22 22:28:57   225人阅读

Message Passing

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1184    Accepted Submission(s): 420


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


思路来源于：点击打开链接

题意：
一个有n个节点的树，每个节点存有一份独一无二的信息，要求用最小的步数，把每个节点的信息共享给所有的节点，问最小步数的方案有多少种。

思路：
通过分析能知最小步数为边的两倍2*（n-1），方案为先将所有信息汇集到一个点，然后再从这个点发散到所有边，这样的策略是最优的。比如先汇集到u点的方案数，那么就是以u点为根的树的拓扑排序数，现在问题变为求树上每个点的拓扑排序数，用树形dp解决。
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，t为fa除去u子树的树，那么有
dp[fa]=dp[t]*dp[u]*C(n-1,num[u]);
将u看做跟时，合并t子树和原来的子树，有
dp1[u]=dp[u]*dp[t]*C(n-1,num[u]-1);
联立两个式子，有dp1[u]=dp[fa]*num[u]/(n-num[u]);
答案即为∑dp[u]^2.

代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define maxn 2000005
#define MAXN 4000005
#define INF 0x3f3f3f3f
#define mod 1000000007
#define eps 1e-6
const double pi=acos(-1.0);
typedef long long ll;
using namespace std;

int n,m,cnt;
int head[maxn],num[maxn];
ll dp[maxn],inv[maxn],fac[maxn],ans;
struct node
{
    int v,next;
} edge[MAXN];

void addedge(int u,int v)
{
    cnt++;
    edge[cnt].v=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}
void egcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0)
    {
        x=1,y=0;
        return ;
    }
    egcd(b,a%b,x,y);
    ll t=x;
    x=y;
    y=t-a/b*x;
}
void presolve()
{
    int i;
    fac[0]=1;
    for(i=1; i<=1000000; i++)
    {
        ll x,y;
        fac[i]=(fac[i-1]*i)%mod;
        egcd(fac[i],mod,x,y);
        x=(x+mod)%mod;
        inv[i]=x;
    }
}
void dfs1(int u,int fa)
{
    num[u]=dp[u]=1;
    int i,v;
    for(i=head[u]; i; i=edge[i].next)
    {
        v=edge[i].v;
        if(v==fa) continue ;
        dfs1(v,u);
        num[u]+=num[v];
        dp[u]=(dp[v]*dp[u])%mod;
        dp[u]=(dp[u]*inv[num[v]])%mod;
    }
    dp[u]=(dp[u]*fac[num[u]-1])%mod;
}
void dfs2(int u,int fa)
{
    int i,v;
    if(u!=1)
    {
        ll x,y;
        egcd(n-num[u],mod,x,y);
        dp[u]=((dp[fa]*num[u])%mod*x)%mod;
    }
    ans=(ans+(dp[u]*dp[u]))%mod;
    for(i=head[u]; i; i=edge[i].next)
    {
        v=edge[i].v;
        if(v==fa) continue ;
        dfs2(v,u);
    }
}
int main()
{
    int i,j,t;
    presolve();
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        cnt=0;
        memset(head,0,sizeof(head));
        int u,v;
        for(i=1; i<n; i++)
        {
            scanf("%d%d",&u,&v);
            addedge(u,v);
            addedge(v,u);
        }
        dfs1(1,0);
        ans=0;
        dfs2(1,0);
        printf("%I64d\n",ans);
    }
    return 0;
}

 

hdu 4661 Message Passing （思维 dp求拓扑排序数）


联系
我们