本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-05-17 20:30:35

这是 CF1824B 枚举点计算贡献的 $O(n)$ 做法。

step1

称有人的结点为关键点。

实际上 $\min_u \sum_{i} dis(u,i)$ 的性质就是重心，即点 $u$ 是好的当且仅当以 $u$ 做为根时，每个子树中关键点的数量均 $\le \lfloor \dfrac{k}{2} \rfloor$，因为从这样的点向任意方向移动都只会使距离和不减。

step2

接下来的思路非常直接：枚举每个点 $u$，然后计算有多少关键点的分布方式使得 $u$ 满足 step1 中提到的性质。

直接算不太行，但是注意到关键点数 $> \lfloor \dfrac{k}{2} \rfloor$ 的子树至多有一个，所以可以考虑容斥，于是点 $u$ 的贡献有式子：

$$ \sum_{(u,v) \in E} \sum_{i = \lfloor \frac{k}{2} \rfloor + 1}^{k} \binom{siz_v}{i} \binom{n-siz_v}{k-i} $$

直接抄式子，能得到一个 $O(n^2)$ 做法。

step3

注意到 $\sum_{i = \lfloor \frac{k}{2} \rfloor + 1}^{k} \binom{siz_v}{i} \binom{n-siz_v}{k-i}$ 这整个式子只跟 $siz_v$ 有关系所欲我们不妨设：

$$ f_x = \sum_{i = \lfloor \frac{k}{2} \rfloor + 1}^{k} \binom{x}{i} \binom{n-x}{k-i} $$

可以考虑 $O(n)$ 递推出来 $f_{1 \dots n}$。具体来说，我们有：

$$ \begin{aligned} L &= \lfloor \frac{k}{2} \rfloor + 1\ f_{x+1} - f_{x} &= \sum_{i = L}^k \binom{x+1}{i}\binom{n-x-1}{k-i}-\binom{x}{i}\binom{n-x}{k-i}\ &= \sum_{i=L}^k \binom{x}{i-1}\binom{n-x-1}{k-i} + \binom{x}{i}\binom{n-x-1}{k-i} - \binom{x}{i}\binom{n-x}{k-i}\ &= \sum_{i=L-1}^{k-1} \binom{x}{i}\binom{n-x-1}{k-i-1}-\sum_{i=L}^{k-1} \binom{x}{i}\binom{n-x-1}{k-i-1}\ &= \binom{x}{\lfloor \frac{k}{2} \rfloor} \binom{n-x-1}{k - \lfloor \frac{k}{2} \rfloor - 1} \end{aligned} $$

于是我们就能 $O(n)$ 递推出 $f_{1 \dots n}$ 了，当然这个差分也可以考虑组合意义而不是暴力推：考虑 $f_{x+1}$ 比 $f_x$ 多的部分实际上就是前 $x+1$ 个点中恰好有 $\lfloor \frac{k}{2} \rfloor + 1$ 个关键点且第 $x+1$ 个点必为关键点的情况。

总复杂度 $O(n)$，所以这题实际上可以加强到带点权 $n \le 1 \times 10^7$。

代码：

#include <bits\/stdc++.h>
#define lowbit(x) (x & -x)
#define eb emplace_back
#define pb push_back
#define mp make_pair
using namespace std;

typedef long long ll;
const int N = 2e5+5;
const int Mod = 1e9+7;

int n, k, siz[N];
int ans;
int f[N];

ll fac[N], ifac[N];

vector<int> T[N];

void dfs(int x, int fa) {
    siz[x] = 1;
    for (int son : T[x]) {
        if (son == fa) continue;
        dfs(son, x);
        siz[x] += siz[son];
    }
}

inline int qpow(int a, int b) {
    ll base = a, ans = 1;
    while (b) {
        if (b & 1) ans = ans * base % Mod;
        base = base * base % Mod;
        b >>= 1;
    }
    return ans;
}

inline void Add(int &a, int b) { a += b; if (a >= Mod) a -= Mod; }
inline ll C(int n, int m) { return n >= m ? fac[n] * ifac[m] % Mod * ifac[n - m] % Mod : 0; }

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        T[u].pb(v);
        T[v].pb(u);
    }

    dfs(1, 0);

    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % Mod;
    ifac[n] = qpow(fac[n], Mod - 2);
    for (int i = n; i; i--) ifac[i - 1] = ifac[i] * i % Mod;

    for (int i = 1; i <= n; i++) {
        f[i] = (f[i - 1] + C(n - i, k - k \/ 2 - 1) * C(i - 1, k \/ 2)) % Mod;
    }

    for (int i = 1; i <= n; i++) {
        Add(ans, C(n, k));
        for (int son : T[i]) {
            int s = siz[son] < siz[i] ? siz[son] : n - siz[i];
            Add(ans, Mod - f[s]);
        }
    }

    printf("%lld", (ll) ans * qpow(C(n, k), Mod - 2) % Mod);
    return 0;
}