Random Access Iterator – 2019徐州网络赛(树形概率DP)

题目链接

https://nanti.jisuanke.com/t/41392

题目大意

在dfs求树深度的过程中,本来在每个点都要遍历一遍它的儿子的,但是现在变成了随机找一个儿子进行遍历,共随机找它的儿子遍,问最终能求到正确的深度的概率。

解题思路

由于正确的概率中既包含了只有一次走到了正确性的道路也包含了多次走到了正确的道路但错误的概率一定是没有一次走到了正确的概率,所以转移的过程中考虑用错误的概率去转移,再用1-错误的概率来求正确的概率。
设dp[u]为从u这个点出发最后能够找到正确的深度的概率。转移中考虑用1减掉全部都走不到正确的深度的概率。
随机的选择一次能走到正确的深度的概率:
p=sum(dp[son])/num(son)
随机的选择一次不能走到正确的深度的概率:
pp=1-p
随机的选择k次一次都没能走到正确的深度的概率:
pp^k
随机的选择k次有一次或多次能走到正确的深度的概率:
dp[u]=1-pp^k

代码

#include <bits/stdc++.h>
const int maxn=1000010;
const int mod=1e9+7;
using namespace std;
int head[maxn],depp[maxn],dp[maxn];
int tot;
struct node{
    int u,v,nxt,deep;
}edge[2*maxn+100];
int maxx;
int qpow(long long a,long long b)
{
    long long ans = 1,base = a;
    while(b!=0)
    {
        if(b&1)
            ans = (ans*base)%mod;
        base = (base*base)%mod;
        b>>=1;
    }
    return ans%mod;
}
//pow(2,mod-2);
void add(int u,int v){
    edge[tot]={u,v,head[u]};
    head[u]=tot++;
}
void dfs(int u,int deep,int fa){
    maxx=max(maxx,deep);
    depp[u]=deep;
    for(int i=head[u];i!=-1;i=edge[i].nxt){
        int v=edge[i].v;
        if(v==fa)
            continue;
        dfs(v,deep+1,u);
    }
}

void dfs1(int u,int deep,int fa){
    if(deep==maxx){
        return;
    }
    int s=0;//孩子的数量
    long long sum=0;//孩子能走到正确的深度的概率和
    for(int i=head[u];i!=-1;i=edge[i].nxt){
        int v=edge[i].v;
        if(v==fa)
            continue;
        s++;
        dfs1(v,deep+1,u);
        if(dp[v]){
            sum=(sum+dp[v])%mod;
        }
    }
    long long p;//当前点能走到正确深度的概率
    p=(sum*qpow(s,mod-2))%mod;
    p=(1-p+mod)%mod;
    p=qpow(p,s);
    p=(1-p+mod)%mod;
    dp[u]=p;
}

int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=0;i<=n;i++){
        head[i]=-1;
    }
    int u,v;
    for(int i=1;i<n;i++){
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    //第一遍dfs处理深度信息,找到树的深度
    dfs(1,1,-1);
    for(int i=1;i<=n;i++){
        if(depp[i]==maxx){
            dp[i]=1;
        }
    }
    //树形DP
    dfs1(1,1,-1);
    cout<<dp[1]<<endl;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注