题解 CF708C 【Centroids】

· · 题解

考虑当我们已经确定了一棵树的重心并以重心为根，有一个显然的结论，对于任一子节点为根的子树大小一定不超过\lfloor\frac{n}{2} \rfloor。

因为去掉重心，树所剩下的每个部分一定不超过\lfloor\frac{n}{2} \rfloor，对于每个部分的每棵子树的大小只能更小。

因此如果我们以树的重心为根，如果一个点x不能成为重心，一定是n-size(x)>\lfloor\frac{n}{2} \rfloor。

例如下面这棵树：

以重心2为根，点3显然不能成为重心，其原因是n-size(3)=8>5即B部分的大小大于\lfloor\frac{n}{2} \rfloor

接下来考虑对这棵树进行改造：

我们要在Part_A中选一条边删除，将其分裂成两个不连续的部分，再将其中一部分与3连接。

下面是一种改造过程：

1.删除边<1,2>，使其Part_A分裂成两部分

2.添加边<2,3>，将分裂出去的部分接成点3的子树

这样，经过改造点3可以成为树的重心。

那么，为了令我们当前的点x尽可能的成为重心，我们就需要使得分裂出去的部分尽可能地大，并直接接在点x上。

即我们要在n-size(x)的部分找最大的且大小不超过\lfloor\frac{n}{2} \rfloor连续的一部分，记其大小为f(x)。

如果n-size(x)-f(x)\le \lfloor\frac{n}{2} \rfloor，那么这个点就可以成为重心，反之则不可以。

那么接下来我们要考虑如何计算出f(x)

记fa(x)为x的父节点。

考虑f(2)的所有决策:

1.$ $n-size(2)\le\lfloor\frac{n}{2} \rfloor$时：$n-size(2) 再来考虑$2$的儿子的决策。 ![](https://cdn.luogu.com.cn/upload/image_hosting/4gi5vvry.png) $n-size(x)$大体分成两部分：$x$的兄弟，和除了$x$与$x$兄弟的部分。 并且这两部分互不干扰： 首先，如果$n-size(x)>\lfloor\frac{n}{2} \rfloor$，其断开的边不可能是与其父节点相连的边$<fa(x),x>$。 那么所删的一条边只能是其兄弟子树与父节点相连的一条边或不包括$fa(x)$的部分的一条边。 设$d(x)$为以$x$为根的子树中大小不超过$\lfloor\frac{n}{2} \rfloor$的最大子树，设$B(x)$为$x$的兄弟节点集合。 那么有转移方程 $$ f(x)=\max\left\{ \begin{aligned} &n-size(x)\ (n-size(x) \le \lfloor \frac{n}{2}\rfloor)\\ &\max\limits_{j\in B(x),j\not=x}\{d(j)\} \\ &f(fa(x)) \end{aligned} \right. $$ 这里有一个常用技巧：令$d(x,0)$为最大，$d(x,1)$为次大 那么有转移方程： $$ f(x)=\max\left\{ \begin{aligned} &n-size(x)\ \ \ (n-size(x) \le \lfloor \frac{n}{2}\rfloor)\\ & d(fa(x),0)\ \ \ (d(x,0)\not=d(fa(x),0))\\ & d(fa(x),1)\ \ \ (d(x,0)=d(fa(x),0))\\ &f(fa(x)) \end{aligned} \right. $$ 接下来考虑计算$d(x)

因为我们以重心为根，因此d(x,0)即为以x的子节点为根的最大的子树的大小。在更新d(x,0)时顺便更新d(x,1):

\begin{aligned} &event:size(son)>d(x,0): \\ &do:d(x,1)=d(x,0),d(x,0)=size(son)\\ &envet:d(x,0)\ge size(son)>d(x,1):\\ &do:d(x,1)=size(son) \end{aligned}

这样的复杂度是O(n)的。

代码:

#include <iostream>
#include <cstring>

namespace wxy{
    const int N = 4e5 + 10;
    int size[N],head[N],fail[N << 1],edge[N << 1],tot = 0;
    int n,root = 1,ans = 1e9;
    bool vis[N];
    int d[N][3],f[N];
    inline void add(int x,int y){
        edge[++tot] = y;
        fail[tot] = head[x];
        head[x] = tot;
    }
    inline void insert(int x,int y){add(x,y);add(y,x);}
    void dfs_root(int u){
        int max_part = 0;
        size[u] = 1;
        vis[u] = true;
        for (int i = head[u];i;i = fail[i]){
            int v = edge[i];
            if (vis[v]) continue;
            dfs_root(v);
            size[u] += size[v];
            max_part = std::max(max_part,size[v]);
        }
        max_part = std::max(max_part,n - size[u]);
        if (max_part < ans){
            ans = max_part;
            root = u;
        }
    }
    void dfs_d(int u){
        vis[u] = true;
        size[u] = 1;
        for (int i = head[u];i;i = fail[i]){
            int v = edge[i];
            if (vis[v]) continue;
            dfs_d(v);
            size[u] += size[v];
            if (size[v] > d[u][0]){
                d[u][1] = d[u][0];
                d[u][0] = size[v];
            }else if (size[v] > d[u][1]){
                d[u][1] = size[v];
            }
        }
    }
    void dfs_f(int u,int fa){
        vis[u] = true;
        if (d[fa][0] == size[u]) f[u] = std::max(d[fa][1],f[fa]);
        else f[u] = std::max(d[fa][0],f[fa]);
        if (n - size[u] <= n / 2) f[u] = std::max(f[u],n - size[u]);
        if (u == root) f[u] = 0;
        for (int i = head[u];i;i = fail[i]){
            int v = edge[i];
            if (vis[v]) continue;
            dfs_f(v,u);
        }
    }
    void main(){
        std::cin >> n;
        for (int i = 1; i < n; i++){
            int x,y;
            std::cin >> x >> y;
            insert(x,y);
        }
        dfs_root(1);

        memset(vis,false,sizeof vis);
        memset(size,0,sizeof size);
        dfs_d(root);
        memset(vis,false,sizeof vis);
        dfs_f(root,0);
        //for (int i = 1; i <= n; i++) std::cout << f[i] << " ";
        //std::cout << std::endl;
        for (int i = 1; i <= n; i++){
            if (size[i] >= n / 2) std::cout << 1 << " ";
            else if (n - size[i] - f[i] <= n / 2) std::cout << 1 << " ";
            else std::cout << 0 << " ";
        }

    }
}signed main(){wxy::main();return 0;}