题解 | #I题 给给#
给给
https://ac.nowcoder.com/acm/contest/275/I
线性期望dp
因为是求最终被染色的节点数,对于每个节点分开考虑 如果第i个节点被在k次操作里染色的概率为p,则它的对期望的贡献为 pi*1;所以总的期望E = 所有节点被选的的概率之和。对于第i个节点被选的概率不好求,但是可以求它的对立事件,在k次操作里面都不被选的概率q,所以p = 1-q; 一次的所有选择两个点的情况为C(n,2)+n(一个节点被选两次)。一个点不被选的所有情况即为 每次选的点都是子树里面的两个点。
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e6+5;
const int mod = 1e9+7;
int last[N],tot;
struct Node{
int to,next;
}a[N*2];
ll ans;
int n;
ll k;
int sz[N];
ll f[N];
void add(int u,int v){
tot++;
a[tot].to = v;
a[tot].next = last[u];
last[u] = tot;
}
ll read(){
int f = 1;
ll ans = 0;
char ch = getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') f = -1;
ch = getchar();
}
while(ch<='9' && ch>='0'){
ans = ans*10+ch - '0';
ch = getchar();
}
return ans*f;
}
ll Pow(ll x,ll y){
ll tot = 1;
while(y){
if(y&1) tot =tot*x%mod;
x = x*x%mod;
y >>= 1;
}
return tot;
}
ll C(int n,int m){
if(m>n) return 0;
return (f[n]%mod * (Pow(f[n-m],mod-2)%mod *Pow(f[m],mod-2)%mod)%mod)%mod;
}
ll cnt;
void dfs(int u,int fa){
sz[u] = 1;
ll num = 0;
for(int i = last[u];i>=0; i =a[i].next){
int v = a[i].to;
if(v==fa) continue;
dfs(v,u);
sz[u]+=sz[v];
num = (num%mod + C(sz[v],2)%mod+sz[v]%mod)%mod;//子树里面选择两个点
}
num = (num%mod + (n - sz[u])+C(n - sz[u],2)%mod)%mod;//父亲子树里选两个节点
ll p = (num%mod * Pow(cnt,mod-2)%mod)%mod;//u节点一次操作不被选的概率
ans = (ans%mod+(1-Pow(p,k)%mod +mod)%mod)%mod;
}
signed main(){
f[0] = 1;
for(int i = 1;i<N;i++) f[i] = f[i-1]*i%mod;
n = read(),k = read();
cnt = C(n,2)+n;
memset(last,-1,sizeof(last));
tot = -1;
int v ,u;
for(int i = 1;i<=n-1;i++){
u = read();
v = read();
add(u,v);
add(v,u);
}
ans = 0;
dfs(1,0);
cout<<ans<<endl;
return 0;
}