CF1824B2 题解

· · 题解

这是 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;
}