题解 CF708C 【Centroids】

· · 题解

\mathsf{Solution\space For\space CF708C}

Upd:非常非常不好意思，这个屑贴错了代码，现在已经更新
被这个问题困扰到的欢迎私信D死这个屑

\mathcal{By\space ShadderLeave}

提供一种思想上和其他题解不一样（也许会更容易理解？）的解法

\mathsf{Description}

给出一棵树，你可以选择断掉其中的一条边将其重新连接到任意一个节点上，使其形成一棵新树，请问有多少个节点可以通过这种操作成为树的重心？
输出一行 N 个数，第 i 个数字是 0/1 表示第 i 个节点 可以/不可以 成为重心

0\le N\le 4\times 10^5

\mathsf{Analysis}

重心给出的定义是所有的子树大小都小于等于 \lfloor \dfrac{N}{2}\rfloor 的节点，所以说，如果一个节点不是重心，就表示这个节点有一个子树的大小超出了 \lfloor \dfrac{N}{2}\rfloor（而且只有一个），我们只需要在这个超出了 \lfloor\dfrac{N}{2}\rfloor 的子树中挑选一个更小子树断掉他然后连到当前节点上来。

问题是，这个大小超出 \lfloor \dfrac{N}{2}\rfloor 的子树中有没有这种断掉之后可以使得其大小减小到 \lfloor \dfrac{N}{2}\rfloor 以下的这种小子树呢？

而且这是一棵无根树，形态确定不了，现在所叙述的 “子树” 可能是其父亲节点，一切都似乎变得很麻烦....

但是现在如果我们事先就先找到一个重心作为根，似乎就会有一些美妙的性质。

如果一个节点 u 不是重心，那么一定是其父节点所在的大小为 N-sz[u] 的子树超出了限制（因为以重心为根的时候所有子树的大小都不会超过 \lfloor \dfrac{N}{2}\rfloor，继续向下走的时候深度更深的子树大小只会更小，所以问题一定出在父节点处）

这就启发我们记录一个信息：对于一个节点 u，记录一个除了子树 u 以外的、大小最大但是不超出 \lfloor \dfrac{N}{2}\rfloor 的子树大小，设为 cut[u]，因为问题一定是出在非子树 u 的部分，所以当一个节点不是重心的时候我们只需要判断 N-sz[u]-cut[u]\le\lfloor\dfrac{N}{2}\rfloor 是否成立即可

简化完一圈，就是要求所有节点除了本身以外的部分中不超出 \lfloor\dfrac{N}{2}\rfloor 的最大子树大小，这就是一个换根DP问题了。

设 Max[u] 为子树 u 中的不超出限制的最大子树大小，在进行dfs的时候我们带一个参数，即节点 u 的祖先中的最大的不超出限制的子树大小，设为 maxx，那么有：

maxx=max(maxx,N-sz[u])\space \mathsf{if}(N-sz[u]\le\lfloor\dfrac{N}{2}\rfloor)

同时 cut 的转移写成

cut[v]=max(maxx,Max[u])\space v\in son[u]

如果你这么写的话那你就太naive了（一转攻势

因为很明显 Max[u] 很有可能就是子树 v 的大小，这时候应该选取子树 u 中的次大值，所以要同时记录最大和次大，分别为 Max[u][0/1]

cut[v]=max(maxx,Max[u][0])\space \mathsf{if}(sz[v]\ne Max[u][0]) cut[v]=max(maxx,Max[u][1])\space \mathsf{if}(sz[v]==Max[u][0])

还有啥细节就看代码吧qaq

\mathsf{Code}

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=400007;
int N;
struct E{
    int u,v;
}e[maxn<<1];
int first[maxn],nt[maxn<<1],ES;
inline void addE(int u,int v)
{
    e[++ES]=(E){u,v};
    nt[ES]=first[u];
    first[u]=ES;
    return ;
}
inline int R()
{
    char c;
    int re;
    while((c=getchar())>'9'||c<'0');
    re=c-48;
    while((c=getchar())>='0'&&c<='9')
    re=re*10+c-48;
    return re;
}
int fa[maxn],sz[maxn];
int rt;//rt是找到的重心 
void dfs1(int u)
{
    int v;
    sz[u]=1;
    bool f=true;
    for(int i=first[u];i;i=nt[i])
    {
        v=e[i].v;
        if(v==fa[u]) continue;
        fa[v]=u;
        dfs1(v);
        sz[u]+=sz[v];
        if(sz[v]>N/2) f=false;
    }
    if(N-sz[u]>N/2) f=false;
    if(f) rt=u;
    return ;
}
int Max[maxn][2];//子树u中size最大的/次大的子树大小
void dfs2(int u)
{
    int v;
    sz[u]=1;
    for(int i=first[u];i;i=nt[i])
    {
        v=e[i].v;
        if(v==fa[u]) continue;
        fa[v]=u;
        dfs2(v);
        sz[u]+=sz[v];
        if(sz[v]>N/2) continue;//排除掉大于N/2的
        if(sz[v]>Max[u][0]) Max[u][1]=Max[u][0],Max[u][0]=sz[v];
        else if(sz[v]>Max[u][1]) Max[u][1]=sz[v];
    }
    return ;
}
int cut[maxn];
bool ans[maxn];
void dfs3(int u,int maxx)
{
    int v;
    cut[u]=maxx;
    for(int i=first[u];i;i=nt[i])
    {
        v=e[i].v;
        if(v==fa[u]) continue;
        if(N-sz[u]<=N/2) maxx=max(maxx,N-sz[u]);//也许父亲的部分能直接构成子树 
        if(Max[u][0]==sz[v]) dfs3(v,max(maxx,Max[u][1]));//如果v即为最大的子树那么要用次大值
        else dfs3(v,max(maxx,Max[u][0]));
    }
    if(N-sz[u]-cut[u]<=N/2||u==rt) ans[u]=true;
    return ;
}
int main()
{
    N=R();
    int u,v;
    for(int i=1;i<N;i++)
    {
        u=R();v=R();
        addE(u,v);
        addE(v,u);
    }
    dfs1(1);
    fa[rt]=0;//注意清空fa 
    dfs2(rt);
    dfs3(rt,0);
    for(int i=1;i<=N;i++)
    if(ans[i]) putchar('1'),putchar(32);
    else putchar('0'),putchar(32);
    return 0;
}
\huge \mathcal{The\space End}

谢谢管理大大审核^_^