ABC149F
*2208
题意
给定一个 \(n\) 个节点的树，每个点的颜色 \(\frac{1}{2}\) 概率黑色，\(\frac{1}{2}\) 概率白色，问这棵树上节点数最少的，包括所有黑色节点的连通块的白色节点的数量的期望。答案对 \(10^9+7\) 取模。
\(n \leq 2×10^5\)，AT中文版一开始的翻译莫名其妙让 \(n\) 缩水一倍导致我 RE 了一发。
题解
一开始以为是妙妙 DP，推了很久转移。后面发现是正难则反，对于每个点算贡献。
考虑一个点在什么情况下 不会 被记入答案。一种情况是其本身是黑点，不会直接贡献答案，一种情况则是其不被任何一个连通块包含。
对于不被任何一个连通块包含的情况，只有两种可能：一种是全部的黑点都在它的其中一个子树中（这里暂时把它看做根），一种是没有黑点。
设 \(siz\) 表示一个点的子树大小，当前点为 \(u\)，则（除自己之外）没有黑点的概率是 \(2^{-(n-1)}\)，全部的黑点都在子树 \(v\) 中的概率为 \(2^{-(n-siz_v-1)}-2^{-(n-1)}\)，全部加起来，然后乘上自身要作为白点的 \(\frac{1}{2}\) 即为点 \(u\) 的贡献。
最后累加所有点的贡献即为答案。
代码
const ll maxn=2e5+5,mod=1e9+7;
vector<ll>e[maxn];
ll ksm(ll x,ll k){ll res=1;for(;k;k>>=1,x=x*x%mod)if(k&1)res=res*x%mod;return res;}
ll n;
ll ans;
ll inv[maxn],siz[maxn];
ll neg(ll x){
return mod-x;
}
void dfs(ll x,ll fa){
ll res=1;
siz[x]=1;
res=(res+neg(inv[n-1]))%mod;
for(auto v:e[x]){
if(v==fa)continue;
dfs(v,x);
siz[x]+=siz[v];
res=(res+neg((inv[n-siz[v]-1]+neg(inv[n-1]))%mod))%mod;
}
res=(res+neg((inv[siz[x]-1]+neg(inv[n-1]))%mod))%mod;
res=res*inv[1]%mod;
ans=(ans+res)%mod;
return ;
}
void solve(){
n=R;
inv[0]=1,inv[1]=ksm(2,mod-2);
for(ll i=2;i<=n;i++)inv[i]=inv[i-1]*inv[1]%mod;
for(ll i=1;i<n;i++){
ll x=R,y=R;
e[x].push_back(y);
e[y].push_back(x);
}
dfs(1,0);
we(ans);
return ;
}