CF1824B2 LuoTianyi and the Floating Islands (Hard Version) - 概率期望 - 树的重心 -

题目链接：https://codeforces.com/contest/1824/problem/B2

题解：
考虑一棵 \(n\) 个点的树，假如已经选定了 \(k\) 个特殊点，如何判断某一个点是否为好点？
显然将这个点提到根没有影响，那么好点的充要条件是对于所有子树的 \(S_u\) 值都 \(\leq k/2\)，这里 \(S\) 代表 \(u\) 子树中的特殊点的个数
证明完全可以考虑重心，只不过这里根可能不是特殊点（如果是特殊点的话，直接把所有非特殊点删去，和重心完全一样），可以发现不影响证明（可以将这个非特殊点合并到相邻的特殊点上，然后删去非特殊点）
这样，我们就找到了一个点是好点的条件。现在考虑对于任意的 \(k\) 个点
考虑指定某一点为根，这里有一个很妙的操作：指定根之后就可以将点的贡献拆到这个点与父亲的边上了。考虑一个边是否为“好边”，显然判断方法就看这条边左边的树的 \(S\) 值是否和右边的 \(S\) 一样，都是 \(k/2\)（由于 \(\leq k/2\)，且只有两个部分，那么肯定都得相等），也就是说这个边是好边的概率是

注意好边的定义是两边的点都是好点，因此期望点的个数期望好边的个数 +1，也就是 \(1+\sum p\)

代码：

// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define pii pair<int,int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, mod = 1e9+7, maxn = 2e5+5;

int fac[maxn], inv[maxn],inv2;
vector<int>g[maxn];

int pw(int x,int y){
	if(!y)return 1;
	if(y == 1)return x;
	int mid=pw(x,y>>1);
	if(y&1)return 1ll*mid*mid%mod*x%mod;
	return 1ll*mid*mid%mod;
}

int C(int x,int y){
	if(x < y)return 0;
	return 1ll*fac[x]*inv[y]%mod*inv[x-y]%mod;
}

int sz[maxn];

int ans = 0, iv; 
void dfs(int x,int fat=0){
	sz[x] = 1;
	for(int u : g[x])if(u != fat){
		dfs(u, x);
		sz[x] += sz[u];
	}
}

signed main(){
	inv2=pw(2,mod-2);
	fac[0] = inv[0] = 1;
	for(int i=1;i<=maxn-5;i++)fac[i] = 1ll*fac[i-1]*i%mod;
	inv[maxn-5] = pw(fac[maxn-5], mod-2);
	for(int i=maxn-6;i>=1;i--)inv[i] = 1ll*inv[i+1]*(i+1)%mod;
	
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=1;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		g[x].pb(y), g[y].pb(x);
	}
	
	if(k %2 == 1){
		puts("1");
		return 0;
	}
	
	dfs(1);
	iv = pw(C(n,k), mod-2);
	for(int i=1;i<=n;i++)
		(ans += 1ll * C(sz[i], k/2) * C(n-sz[i], k/2)%mod) %= mod;
	printf("%d\n",(1ll * ans * iv + 1) % mod);
	
	return 0;
}