题目链接：https://nanti.jisuanke.com/t/41392
题目大意：从根节点开始，求某棵树的深度，从父亲结点开始，等概率达到每个子节点，问正确求得深度的概率。
解题思路：记 dp[u] 表示以 u 为根的子树，从 u 开始运行题面算法，得到正确答案的概率。深度最深的叶子 u 的 dp[u] = 1 ，其他叶子 dp[u] = 0。转移时，考虑取不到的概率即可。
dp【u】=1-（1-（∑dp【v】）/cnt【u】）^cnt【u】。cnt【u】为结点u的子节点的个数。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=1e9+7; const int maxn=1e6+5; struct st{ int to,next; }stm[maxn*2]; int tot; int head[maxn]; void add(int u,int v){ stm[tot].to=v; stm[tot].next=head[u]; head[u]=tot++; } ll qpow(ll n,ll m){ ll ans=1; while(m){ if(m&1)ans=ans*n%mod; m/=2; n=n*n%mod; } return ans; } int dep[maxn]; int maxdep; int dp[maxn]; int cnt[maxn]; void dfs1(int u,int fa){ dep[u]=dep[fa]+1; maxdep=max(maxdep,dep[u]); for(int i=head[u];~i;i=stm[i].next){ int to=stm[i].to; if(to==fa)continue; cnt[u]++; dfs1(to,u); } return ; } void dfs2(int u,int fa){ ll tem=0; for(int i=head[u];~i;i=stm[i].next){ int to=stm[i].to; if(to==fa)continue; dfs2(to,u); tem+=dp[to]; } if(dp[u]==0){ tem=tem*qpow(cnt[u],mod-2)%mod; tem=(1-tem+mod)%mod; dp[u]=(1-qpow(tem,cnt[u])+mod)%mod; } } int main(){ int n; int u,v; memset(head,-1,sizeof(head)); tot=0; scanf("%d",&n); for(int i=1;i<n;i++){ scanf("%d%d",&u,&v); add(u,v); add(v,u); } dfs1(1,0); for(int i=1;i<=n;i++){ if(dep[i]==maxdep){ dp[i]=1; } else{ dp[i]=0; } } dfs2(1,0); //cout<<maxdep<<endl; // for(int i=1;i<=n;i++) printf("%lld\n",dp[1]); return 0; }
The Preliminary Contest for ICPC Asia Xuzhou 2019 J. Random Access Iterator（树形DP+概率DP）
原文：https://www.cnblogs.com/Zhi-71/p/11489002.html