P7565 [JOISC 2021] ビーバーの会合 2 (Day3) - Solution

· · 题解

刚开始想了一个假贪心还觉得对完了。

首先，可期待点类似于树的重心，不过这是虚树的重心。

给出一个重要观察：可期待点构成树上的一条链。

否则，取出该不可期待点，该点必定存在一个子树，关键点数大于它的其余子树之和。而两个可期待点至少有一个不在该子树中，该可期待点往这个子树方向走贡献变小，矛盾。

注意到我们取出该点（关键点意义下）最小的可期待点子树，走到该点贡献变小，矛盾。

既然可期待点构成树上的一条链，很显然可以考虑点分治。

具体到点分治上，设当前点分治的根为 x。我们不妨枚举一端 u。

假设要求关键点数为 k，我们钦定路径 u \to v。如果我们可以把 \frac{k}{2} 塞进 u 子树里面，把 \frac{k}{2} 塞进 v 子树里面，那么这就构造出了一种合法方案。否则，我们肯定没办法构造出来另一种方案，因为不管怎么样，我们都不能在三个方向上同时布满关键点，还让 u \to v 有贡献。

然后我们相当于 sz_u \ge \frac{k}{2} 就可能贡献到 k 上，这个东西我们可以直接搞成后缀最大值，并且考虑与前面的某个满足相同条件的 v 合并。

时间复杂度 \Theta(n \log n)。

int n; vec<int> g[maxn]; int vis[maxn], rt, sz[maxn], W, S, d[maxn], ans[maxn];
void getrt(int u, int f = 0) {
    sz[u] = 1; int x = 0;
    for (int v : g[u]) {
        if (v == f || vis[v]) continue;
        getrt(v, u), sz[u] += sz[v];
        if (sz[v] > sz[x]) x = v;
    }
    int k = max(sz[x], S - sz[u]);
    if (k < W) rt = u, W = k;
}
int s[maxn], t[maxn];
void dfs(int u, int f) {
    d[u] = d[f] + 1; 
    for (int v : g[u]) if (!vis[v] && v != f) dfs(v, u);
    s[sz[u]] = max(s[sz[u]], d[u]);
}
void calc(int u) {
    vis[u] = 1; d[u] = 0; getrt(u, 0);
    for (int v : g[u]) {
        if (vis[v]) continue;
        dfs(v, u);
        per(i, sz[v] - 1, 1) s[i] = max(s[i], s[i + 1]);
        rep(i, 1, sz[v]) ans[i * 2] = max(ans[i * 2], s[i] + t[i]);
        rep(i, 1, sz[v]) t[i] = max(t[i], s[i]), s[i] = 0;
    }
    rep(i, 1, sz[u]) s[i] = t[i] = 0;
    for (int v : g[u]) {
        if (vis[v]) continue;
        rt = 0, S = sz[v], W = 1e9;
        getrt(v, u); calc(rt);
    }
}
int main() {
    scanf("%d", &n); 
    if (n == 1) puts("1"), exit(0);
    for (int i = 1, u, v; i < n; i++) scanf("%d%d", &u, &v), g[u].pb(v), g[v].pb(u);
    rt = 0, S = n, W = 1e9; getrt(1, 0); calc(rt);
    rep(i, 1, n) printf("%d\n", (i & 1) ? 1 : ans[i] + 1);
    return 0;
}