题解：P7565 [JOISC 2021] ビーバーの会合 2 (Day3)

前言

我太菜了，不会 的 LCA 写法。

Solution

转化

首先，根据树重心的性质，树中所有结点到某个结点的距离和中，到重心的距离和最小。

证明见 OI wiki。

不过在这个问题中是有点权的，但是我们可以通过相似的方法证明重心仍然是距离和最小的那个点。

注意：接下来所有的“重心”若不特别说明，均讨论的是带点权树上的重心。

问题

所以我们现在将问题转化为了求树上有若干个点有 权值时的可能重心数量。

考虑一个点可能为重心的条件。

容易想到，为了“分摊”带权点，若以某点为树根，则这个点至少有两个儿子的子树的大小要不小于 ，这样才能容纳的下。

结论 1

但是我们发现 为奇数时有点问题，此时 不是整数，我们上面也没有给出任何取整。

然后就有一个暴论： 为奇数时只会有一个点是重心。

证明如下：

假设当前已经发现了一个重心 ，还存在另一个重心 。

根据重心定义， 的所有子树的权值和均小于 （注意此时 是奇数所以是小于不是小于等于）， 同样如此。

所以以 为根， 的儿子的子树中，包含 的子树权值和小于 ，其余子树的权值和之和加上 的权值的和大于 。

所以以 为根， 的儿子的子树中，包含 的子树权值和大于 。

这与 是重心的假设矛盾，所以假设错误，应当不存在第二个重心。

但是显然树上无论怎样一定会有一个重心。

所以 为奇数时有一个重心且仅有一个重心。

证毕。

上面的证明可能有点抽象，放个图方便理解。

好吧我画画还是太差了。

结论 2

现在需要高效的数出有多少点满足重心条件，我们从大到小考虑 ，这样条件会变得越来越松，然后我们发现有一个喜人的性质：满足条件的点是一个连通块。

这个结论可以跟上面证“ 为奇数时仅有一个重心”相似的方法证，就是假设有两个不连通的满足条件的点，然后发现它们路径上的点也应当是满足条件的，这个证明是简单的，且前面有类似的证明过程，就不赘述了。

因为原图是一棵树，所以这个连通块也是个树。

结论 3

那么答案是多少呢，其实就是这个连通块的直径。

因为若选择成为重心的点不形成链，那么会出现下图情况：

此时若想让 点同时可以成为重心，那么以 号点为重心，黄圈内部分权值和就不大于 ，红圈内部分权值和就不小于 。

若红圈内权值和大于 ， 号点就不可能成为重心，因为它有一个儿子的子树大小大于 。

若红圈内权值和等于 ，且 号是重心，若想要 号点是重心，则绿圈、蓝圈内权值和也要等于 ，这与总权值和为 矛盾。

所以成为重心的点不可能出现“分叉”，也就必定是条链，那当前最优答案就是这个连通块的直径。

最终做法

此时我们考虑以原树（无权树）的重心为根，这样每个非根节点的子树不大于 ，而子树外的点的数量就肯定不小于 ，也就肯定不小于任意的 。

此时我们就只用考虑这样每个非根节点的子树大小。

具体地，我们以原树重心为根，dfs 一遍处理出每个非根节点的子树大小。再把这些点按照子树大小倒序排序。

开始时连通块只有原树重心一个点。

然后倒序遍历 ，对于奇数 ，答案是 ，对于偶数 ，如果当前子树大小最大的点的子树大小不小于 ，就将它加入连通块，更新连通块直径，更新对应 的答案。

更新连通块直径用到了另一个树直径的性质，就是若原树直径端点对是 ，加入点 ，则新直径端点是 三者之一。

为了更新直径，我们需要求 LCA 以求树上两点之间距离，用什么方法求都行。

遍历完就得到了答案。

时间复杂度

求重心 ，求子树大小 ，排序可用桶排 ，求 LCA 取决于具体算法，笔者用的欧拉序加 ST 表， 预处理， 查询。

整体 ，但显然可以优化到线性。

Code

#include <bits/stdc++.h>
#define nmf(i, s, e) for (int i = s; i <= e; i++)
#define ref(i, s, e) for (int i = s; i >= e; i--)
namespace FastIO
{
    template <typename T>
    inline void read(T &x)
    {
        short neg = 1;
        char ch;
        while (ch = getchar(), !isdigit(ch))
            if (ch == '-')
                neg = -1;
        x = ch - '0';
        while (ch = getchar(), isdigit(ch))
            x = (x << 3) + (x << 1) + (ch ^ '0');
        x *= neg;
    }
    template <typename T, typename... Args>
    inline void read(T &x, Args &...args)
    {
        read(x);
        read(args...);
    }
    template <typename T>
    inline void read(T *begin, T *end)
    {
        unsigned len = end - begin;
        for (unsigned i = 0; i < len; i++)
            read(*(begin + i));
    }
    template <typename T>
    inline void write(T x)
    {
        if (x < 0)
            putchar('-'), x = -x;
        if (x > 9)
            write(x / 10);
        putchar(x % 10 + '0');
    }
    template <typename T, typename... Args>
    inline void write(T x, Args... args)
    {
        write(x);
        putchar(' ');
        write(args...);
    }
    template <typename T>
    inline void write(T *begin, T *end)
    {
        unsigned len = end - begin;
        for (unsigned i = 0; i < len; i++)
            write(*(begin + i)), putchar(' ');
    }
}
using namespace FastIO;
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
int n;
vector<int> grh[200005];
int ans[200005];
int euler[400005], pos[200005], dep[200005], sz[200005], tim;
int st[400005][19], lg[400005];
int weight[200005];
int centroid; // 重心
void dfs1(int u, int fa) // 找重心，处理欧拉序
{
    euler[++tim] = u;
    pos[u] = tim;
    sz[u] = 1;
    for (auto v : grh[u])
    {
        if (v == fa)
            continue;
        dep[v] = dep[u] + 1;
        dfs1(v, u);
        euler[++tim] = u;
        sz[u] += sz[v];
        weight[u] = max(weight[u], sz[v]);
    }
    weight[u] = max(weight[u], n - sz[u]);
    if (weight[u] <= n >> 1)
    {
        centroid = u;
    }
}
void LCA_init()
{
    lg[0] = -1;
    nmf(i, 1, tim) lg[i] = lg[i >> 1] + 1;
    nmf(i, 1, tim) st[i][0] = euler[i];
    nmf(j, 1, 18) nmf(i, 1, tim - (1 << j) + 1) st[i][j] = (dep[st[i][j - 1]] < dep[st[i + (1 << (j - 1))][j - 1]]) ? st[i][j - 1] : st[i + (1 << (j - 1))][j - 1];
}
int LCA(int x, int y)
{
    int l = pos[x], r = pos[y];
    if (l > r)
        swap(l, r);
    int k = lg[(r - l + 1)];
    return (dep[st[l][k]] < dep[st[r - (1 << k) + 1][k]]) ? st[l][k] : st[r - (1 << k) + 1][k];
}
int dist(int x, int y)
{
    if (x == y)
        return 0;
    if (x == 1)
        return dep[y];
    if (y == 1)
        return dep[x];
    return dep[x] + dep[y] - (dep[LCA(x, y)] << 1);
}
vector<pair<int, int>> q;
vector<int> buc[200005]; // 桶排用桶
void dfs2(int u, int fa)
{
    sz[u] = 1;
    for (auto v : grh[u])
    {
        if (v == fa)
            continue;
        dfs2(v, u);
        sz[u] += sz[v];
    }
    if (u ^ centroid)
        buc[sz[u]].emplace_back(u);
}
void solve()
{
    read(n);
    nmf(i, 2, n)
    {
        int ui, vi;
        read(ui, vi);
        grh[ui].emplace_back(vi);
        grh[vi].emplace_back(ui);
    }
    dfs1(1, 0);
    LCA_init();
    memset(sz, 0, sizeof(sz));
    dfs2(centroid, 0);
    ref(i, n, 1)
    {
        for (auto j : buc[i])
            q.emplace_back(i, j);
    }
    auto it = q.begin();            // 迭代器遍历
    int x = centroid, y = centroid; // 初始时连通块里仅有重心
    ref(i, n, 1)
    {
        if (i & 1)
        {
            ans[i] = 1;
            continue;
        }
        while (it != q.end() && it->first >= (i >> 1))
        {
            // 更新直径
            int New = it->second;
            if (dist(x, New) > dist(x, y))
                y = New;
            if (dist(New, y) > dist(x, y))
                x = New;
            it++;
        }
        ans[i] = dist(x, y) + 1;
    }
    nmf(i, 1, n) write(ans[i]), putchar('\n');
    return;
}
signed main()
{
    int T = 1;
    while (T--)
        solve();
    return 0;
}