Random Access Iterator【树上求概率】

题意：

  现在给一棵以点 \(1\) 为根节点的树，对于当前节点，每一个子节点都有等概率访问，现在访问子节点个数次，问从根节点开始至少能到达一次最深的节点的概率是多少（概率还要求逆元）。
题目链接：https://nanti.jisuanke.com/t/41392

分析：

  概率题，先分析状态。首先，当一个点必然不可能到达最大深度的点时，其概率为 \(0\)；当一个节点是叶子节点并且其深度为最大时，其概率为 \(1\)。对于其他点，就要利用这两个基本条件推出。注意题目中，一个节点要走 \(k\) 次来求出其概率，\(k\) 为其儿子节点的个数。
假设每个点正确的概率为 \(dp[i]\)。
对于一个点，有\(sz\) 个儿子节点，那么走一次错误的概率为：\(p=\frac{1}{sz}*\sum_{i=1}^{sz}{(1-dp[i])}\)，则走一次正确的概率为：\(1-p\)；
所以走 \(sz\) 次，至少正确一次的概率为：\(1-p^{sz}\)。

代码：

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int N=1e6+6;
const int mod=1e9+7;
ll dp[N];
vector<int>pic[N];
int depth[N],md;
ll power(ll a,int b)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
void dfs(int v,int p,int d)
{
    depth[v]=d;
    md=max(md,d);
    for(int i=0;i<pic[v].size();i++)
    {
        int u=pic[v][i];
        if(u==p) continue;
        dfs(u,v,d+1);
        depth[v]=max(depth[v],depth[u]);
    }
}
ll solve(int v,int p)
{
    if(depth[v]<md) return 0;//深度不是答案
    if(pic[v].size()==1) return 1;//叶子节点，且深度为答案
    int sz=pic[v].size()-1;
    if(v==1) sz++;
    ll res=0;
    for(int i=0;i<pic[v].size();i++)
    {
        int u=pic[v][i];
        if(u==p) continue;
        res=(res+1-solve(u,v)+mod)%mod;
    }
    res=res*power(1LL*sz,mod-2)%mod;
    res=power(res,sz);
    return (1-res+mod)%mod;
}
int main()
{
    int n,u,v;
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        pic[u].pb(v);
        pic[v].pb(u);
    }
    md=0;
    dfs(1,0,1);
    ll ans=solve(1,0);
    printf("%lld\n",(ans+mod)%mod);
    return 0;
}