还是头一次往博客园投递文章，其实是从个人总结里搬出来的。
0 题目大意
\(n\) 个点的树上选 \(k\) 个点，定义”好点“为离这 \(k\) 个点的距离之和最小的点，求好点的期望值，模 \(10^9+7\) 。
1 思路
1.1 利用距离之和找性质
我下面这段写得好绕啊，写了挺久的吧，TAT。本来想让豆包帮我改改，感觉豆包改得更加屎山了，所以还是算了。
假设 \(x\) 和 \(y\) 都是”好点“ ，我们设 \(x\) 的子树有 \(s\) 个选中的点，则剩下的选中的点就有 \(k-s\) 个。
考虑从 \(x\) 移动到 \(y\) ，那么 \(x\) 离所有子树里的点都各远了 \(1\)，距离之和增加 \(s\) ，同样地， \(x\) 也离子树外的点都近了 \(1\) ，总距离减少 \(k - s\) 。
因为两点均为好点，所以从 \(x\) 移动到 \(y\) ，距离之和是不变的，增加的距离等于减少的距离。
即：\(s = k-s \Leftrightarrow 2s = k \Leftrightarrow s = \frac{k}{2}\)
1.2 按 k 的奇偶性分类讨论
-
如果 \(k\) 是奇数，那么 \(2s \neq k\) ，也就是说不存在两个”好点“，从一个”好点“出发跳到别的点，距离之和一定会变化，所以只存在一个”好点“。对于所有 \(k\) 为奇数的情况，都可以直接输出一个 \(1\) 。
-
反之，如果 \(k\) 是偶数，就有 \(s = \frac{k}{2}\) 。那么从一个”好点“出发， 必定存在这样一条边，使得去掉这条边之后，树变成的两个连通块中，均有 \(\frac{k}{2}\) 个选中的点。
于是我们枚举每个点的子树大小 \(x\) ：从 \(x\) 里选 \(\frac{k}{2}\) 个节点，方案数是 \((^{x}_{\frac{k}{2}})\) ；同样地，从另一个大小为 \(n-x\) 的连通块里选 \(\frac{k}{2}\) 个节点，方案数是 \((^{n-x}_{\frac{k}{2}})\) 。两个相乘，就是这个点的总方案数，最后再乘上一个概率，也就是除以 \((^{n}_{k})\) ，就是这个点的期望。最后将所有的期望相加即可。
注意：我们本质上是按边枚举的，每种选法的好点数量 \(= 1 +\) 满足条件的边数，所以总和 \(=\) 点的总选法数 \(+\) 边贡献和，最终答案还要加上一个 \((_{k}^{n})\) 表示选点的方案数。
2 代码
没有注释因为懒得写
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll M = 1e9+7;
const int N = 1000005;
ll qp(ll x, ll y) {ll ret = 1;while(y) {if(y&1) ret = ret*x%M;x = x*x%M;y >>= 1;}return ret;
}
ll fc[N], inv[N], ans, sz[N], n, k;
ll C(ll x, ll y) {if(y<x || x<0 || y<0)return 0;return fc[y]*inv[x]%M*inv[y-x]%M;
}vector<ll> g[N];
void dfs(ll u, ll fa) {sz[u] = 1;for(ll v : g[u]) {if(v == fa) continue;dfs(v, u);sz[u] += sz[v];ans = (ans+C(k/2, sz[v])*C(k/2, n-sz[v])%M)%M;}
}int main() {fc[0] = inv[0] = 1;for(ll i=1; i<N; i++)fc[i] = fc[i-1]*i%M,inv[i] = qp(fc[i], M-2);scanf("%lld%lld", &n, &k);if(k&1) {puts("1");return 0;}for(ll i=1, u, v; i<n; i++) {scanf("%lld%lld", &u, &v);g[u].push_back(v);g[v].push_back(u);}ans = C(k, n);dfs(1, 0);printf("%lld\n", ans*qp(C(k, n), M-2)%M);return 0;
}