题解 CF708C 【Centroids】

pyqpyq · 2020-05-02 00:00:42 · 题解

人生第一个最优解（目前）赶紧写篇题解庆祝一下。

当然你得先看完这个。

证明看不懂也没关系。我都不知道我当年怎么口胡的。 但性质三一定要看一看，后面有用。

其实是一道挺值得想的问题，分五个步骤。建议在看每个步骤前先思考，想不出了再看。

Step 1

改造？把一条边拆下来再装上去？怎么弄？

首先这是一个无根树，我们把它变成有根树更好处理。然后一步一步来看。

先是拆边，发现每条边对应一对父子关系，拆掉之后就会把儿子所对应的子树与外界隔绝。

然后加边。为了使加完后还是一棵树，我们需要将加入的边的一头接到这个子树的某个节点上，另一头接到外界的某个节点上。

然而这个外界的节点已经有父亲了，所以这个子树就只能当它的一棵子树了。

总而言之砍一块树下来再补上去。

Step 2

题目问我们那些点可以通过改造变成重心，那我们一个一个看。

对于本来就是重心的节点，我们不用管它。

对于本来非重心的节点，它和重心的区别就在于有一棵子树生长激素分泌过多导致过于庞大。

那我们的任务就是把这个病变的子树通过改造砍成正常的也就是小于等于全树的一半就行了。

不过砍下来的部分还要接到一棵子树上去，我们同时不能让这个子树变得过大。

那么设 a 是被砍的子树的大小，b 是要被接上去的子树的大小，s 是全树的大小，l 是砍下来的树的大小。

列不等式，得：

解得：

Step 3

直接拿这个东西和平衡树上是会发生 TLE/MLE 悲剧的。我们需要分析它。

由于 l 的取值范围的左边界是固定的，我们处理右边界。先处理子树截下来要接到谁上面的问题。

当然，为了使 l 有更多取值，\frac{s}{2}-b 越大越好。而 \frac{s}{2} 是固定的，那么要让 b 尽可能的小。

那什么时候 b 最小呢？直接接到根上面，那样 b 就为 0 了。

所以这个式子变成了这样：

Step 4

好像思路遇到死胡同了？考虑一下重心。

我们会发现被砍的子树一定是包含重心的子树，而且砍的时候只要不把重心砍下来，一定可以满足右边界的条件。

为何加粗呢？因为想通了这个，这题就差不多了。至于为什么，自己思考。我不会告诉你我是懒得画图的。

那么既然这样，我们就砍重心的各个子树。我们从中选取最大的子树以尽量满足左边界条件。如果仍然不能满足就无能为力了，说明当前询问的点本身就不行。

Step 5

然而你直接这么干还是会 WA on test 3 的，死因是没有考虑有两个重心的情况。

遇到这种情况可以换个重心跑两遍，当然也可以直接输出全 1，原因自己思考吧（再次偷懒）。

Code

按上面搞完就你谷最优解了，再换个语言卡个常就 CF 第二解了。

在线膜 CF 最优解。

注意：代码放给你是用来对拍、查错的，不是用来抄袭的。

#include<bits/stdc++.h>
using namespace std;
#define MAXN 400011
int n,u,v,firs[MAXN],neig[MAXN<<1],arri[MAXN<<1],size[MAXN],cent,ncen,rans[MAXN],smax=INT_MIN,nmax=INT_MIN;
int read()
{
    register int re(0),ch;
    do
        ch=getchar();
    while('9'<ch||ch<'0');
    do
        re=re*10+ch-'0';
    while('0'<=(ch=getchar())&&ch<='9');
    return re;
}
int dfs1(int at,int fa)
{
    register int ce(1);
    size[at]=1;
    for(int i=firs[at]; i; i=neig[i])
        if(arri[i]!=fa)
        {
            size[at]+=dfs1(arri[i],at);
            if(size[arri[i]]*2>n)
                ce=0;
        }
    if(ce&&size[at]*2>=n)
    {
        if(cent)
            ncen=at;
        else
            cent=at;
        rans[at]=1;
    }
    return size[at];
}
int dfs2(int at,int fa)
{
    size[at]=1;
    for(int i=firs[at]; i; i=neig[i])
        if(arri[i]!=fa)
            size[at]+=dfs2(arri[i],at);
    return size[at];
}
void dfs3(int at,int fa,int si)
{
    if(size[at]*2+si*2>=n)
        rans[at]=1;
    for(int i=firs[at]; i; i=neig[i])
        if(arri[i]!=fa)
            dfs3(arri[i],at,si);
}
int main()
{
    n=read();
    for(int i=1; i<n; ++i)
    {
        u=read();
        v=read();
        neig[i<<1]=firs[u];
        firs[u]=i<<1;
        arri[i<<1]=v;
        neig[i<<1|1]=firs[v];
        firs[v]=i<<1|1;
        arri[i<<1|1]=u;
    }
    dfs1(1,0);
    if(ncen)
    {
        for(int i=1;i<=n;++i)
        {
            putchar('1');
            putchar(' ');
        }
        return 0;
    }
    dfs2(cent,0);
    for(int i=firs[cent]; i; i=neig[i])
    {
        if(size[arri[i]]>=smax)
        {
            nmax=smax;
            smax=size[arri[i]];
        }
        else if(size[arri[i]]>=nmax)
            nmax=size[arri[i]];
    }
    for(int i=firs[cent]; i; i=neig[i])
        dfs3(arri[i],cent,size[arri[i]]==smax?nmax:smax);
    for(int i=1; i<=n; ++i)
    {
        putchar('0'+rans[i]);
        putchar(' ');
    }
    return 0;
}