线性期望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;
}