牛客周赛 Round 62
树上期望-《经典期望》
小红的树上移动
题目
小红拿到了一棵树,初始所有节点均为白色。小红初始站在1号节点,并将1号节点染红。小红将不断进行移动直到停止:
- 若当前节点的邻点中存在白色节点,则小红随机移动到某个相邻的白色节点,并将该节点染红。
- 若当前节点的邻点中不存在白色节点,则停止移动。
请你帮小红求出最终红点数量的期望。
思路
对于每个点的子节点,概率均为 1 s i z e \frac{1}{size} size1, s i z e size size为该点的子节点个数
dfs跑一遍对于每个节点的概率 p i p_i pi
答案就是 Σ p i × 1 \Sigma p_i\times 1 Σpi×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;
}