Random Access Iterator 2019 ICPC 徐州网络赛（树上概率DP）

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+5;
vector<int>G[N];
const ll p=1e9+7;
int n;
int depth[N];
ll dp[N];
int res=0;
ll quick_pow(ll a, ll b, ll mod)
{
    ll  r = 1, base = a;
    while (b)
    {
        if (b & 1)
            r = (r*base)% mod;
        base = (base*base) % mod;
        b >>= 1;
    }
    return r;
}
void dfs(int u,int d,int fa){
    depth[u]=d;
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(v==fa)continue;
        dfs(v,d+1,u);
    }
    res=max(res,d);
}
void gao(){
    for(int i=1;i<=n;i++){
        if(depth[i]==res){
            dp[i]=1;
        }
    }
}
ll dfs2(int u,int fa){
    if(dp[u]>0)return dp[u]%p;
    ll temp=0;
    int s=G[u].size()-1;
    if(u==1)s++;
    //cout<<u<<" "<<fa<<"  "<<s<<endl;
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(v==fa)continue;
        temp=(temp+quick_pow(s,p-2,p)*dfs2(v,u)%p)%p;
    }
    dp[u]=(1-quick_pow((1-temp+p)%p,s,p)+p)%p;
    return dp[u];
}
int main()
{
    scanf("%d",&n);
    int u,v;
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0,-1);
    gao();
    printf("%lld\n",dfs2(1,-1));
    return 0;
}