牛客周赛 Round 62

树上期望-《经典期望》

小红的树上移动

题目

小红拿到了一棵树，初始所有节点均为白色。小红初始站在1号节点，并将1号节点染红。小红将不断进行移动直到停止：

1. 若当前节点的邻点中存在白色节点，则小红随机移动到某个相邻的白色节点，并将该节点染红。
2. 若当前节点的邻点中不存在白色节点，则停止移动。

请你帮小红求出最终红点数量的期望。

思路

对于每个点的子节点，概率均为$\frac{1}{size}$,$size$为该点的子节点个数

dfs跑一遍对于每个节点的概率$p_i$

答案就是$\Sigma p_i\times 1$

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
using namespace std;
const int N=1e5+5;
const int mod=1e9+7; 
int ans;
vector<int> e[N];
bool vis[N];
int quickpow(int x,int y){
    int res=1;
    while(y){    
        if(y&1) res=(res*x)%mod;            
        x=(x*x)%mod;
        y>>=1;
    }
    return res;
}
int inv(int x){
    return quickpow(x,mod-2);
}
int add(int x,int y){
    return ((x%mod)+(y%mod))%mod;
}
int sub(int x,int y){
    return ((x-y)%mod+mod)%mod;
}
int mul(int x,int y){
    return (x%mod*y%mod)%mod;    
}
void dfs(int v,int p){
//     cout << v << " " << p << endl;
    vis[v] = 1;
    ans = add(ans,p);
    int num = e[v].size();
    if(v!=1) num--;
    for(auto u : e[v]){
        if(vis[u]) continue;
        dfs(u,mul(p,inv((num))));
    }
}
void solve()
{
 	int n;
    cin >> n;
    for(int i = 1 ; i < n ; i ++){
        int x,y;
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    
    dfs(1,1);

    cout << ans << endl;
}

signed main()
{
	std::ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int t=1;
	// cin>>t;
	while(t--){
		solve();
	}
	
	return 0;
}