是 Div2 的 D1 和 D2。
题意
给定一棵 \(n\) 个结点的树，现在有 \(k(k\leq n)\) 个结点上有人。
一个结点是好的当且仅当这个点到所有人的距离之和最小。
求在这 \(n\) 个点中随机取 \(k\) 个点时，好的结点的期望个数，对 \(10^9+7\) 取模。
Easy: \(k\leq 3,n\leq 2*10^5\)
Hard: \(k\leq n\leq 2*10^5\)
Part 1
考虑 Easy 版本。
- \(k=1\) 时，只有一个点是关键点，故答案为 \(1\)。
- \(k=3\) 时，考虑如下三种情况：
当钦定 \(1\) 与 \(2\) 两个点后，考虑第三个点的位置。
- 当三者在一条链上，且第三个点不在前两个点中间时：显然，中间的点是唯一一个“好点”。
- 第三个点在两者中间时：同上，中间的点是唯一一个“好点”。
- 三者不在一条链上：最上方的点是唯一一个“好点”。
得出结论：\(k=3\) 时答案也为 \(1\)。
- \(k=2\) 时，对于每一条链，中间的每一个点都可以成为“好点”。所以只需要统计各个长度的链共有多少条，简单计数即可。
Part 2
进阶到 Hard 版本。
猜想：当 \(k\) 为奇数时，答案恒为 \(1\)。
证明：设好点为 \(x\)，\(k\) 个特殊点组成的序列为 \(a\)，则题目可转化成这样一个式子：
当算式 \(abs(x-a_1)+abs(x-a_2)+......+abs(x-a_k)\) 取到最小值时，\(x\) 的取值满足什么条件？
当 \(k\) 为奇数时，\(x\) 即为 \(a_{k/2+1}\)。对应到题目中，\(x\) 仅会有 \(1\) 个取值。故答案恒为 \(1\)。
当 \(k\) 为偶数时呢？显然，\(x\) 的取值应该在 \(a_{k/2}\) 和 \(a_{k/2+1}\) 之间。转化到题目中，则好点 \(x\) 为子树中的一部分有 \(k/2\) 个特殊点，且子树外也有 \(k/2\) 个特殊点的点。直接统计貌似不太好做，将做法转变一下，我们现在只需要统计每一种方案中“好点”的个数大于等于 \(2\) 的期望和。对于每一种方案，其至少存在一个好点。故最后的答案应加上 \(1\)。
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define db double
#define mkp make_pair
#define pb push_back
#define P pair<int,int>
#define _ 0
const int N=2e5,mod=1e9+7,MOD=1e9+123,inf=1e18;
int T=1,siz[N+10],ans,fac[N+10],inv[N+10],n,k;
vector<int> e[N+10];
int qpow(int a,int b){
int ans=1;
while(b){
if(b&1) ans=(ans*a)%mod;
b>>=1;
a=(a*a)%mod;
}
return ans;
}
void init(){
fac[0]=1;
for(int i=1;i<=N;i++) fac[i]=fac[i-1]*i%mod;
inv[N]=qpow(fac[N],mod-2);
for(int i=N-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
int C(int n,int m){
if(n<m||n<0||m<0) return 0;
return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
void dfs(int x,int fa){
siz[x]=1;
for(int y:e[x]){
if(y==fa) continue;
dfs(y,x);
siz[x]+=siz[y];
ans=(ans+C(siz[y],k/2)*C(n-siz[y],k/2))%mod;
}
}
void solve(){
init();
cin>>n>>k;
if(k&1){
cout<<1;
return ;
}
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
e[u].pb(v),e[v].pb(u);
}
ans=C(n,k);
dfs(1,0);
cout<<ans*qpow(C(n,k),mod-2)%mod;
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
// ios::sync_with_stdio(false),cin.tie(0);
while(T--){
solve();
}
return ~~(0^_^0);
}