CF708C Centroids

有一点思维的换根DP。

如果一个点不是重心，我们则考虑将它其中某一个子树断开在接到这个节点上。于是我们需要在以该节点为根的树中，找一个 $size\le {n\over2}$ 的最大子树。

接下来很容易想到换根 DP。注意到换根时 $f_x$ 的决策点可能就是 $y$。还应该维护预处理次大值。

随便放个代码。

Code

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=4e5+10;
int n;
int tot,head[maxn],ver[2*maxn],ne[2*maxn];
int si[maxn],d[maxn][2],f[maxn],pre[maxn],maxsize[maxn];
int ans[maxn];
void add(int u,int v)
{
    ver[++tot]=v;
    ne[tot]=head[u];
    head[u]=tot;
}
int dp(int x,int fa)
{
    si[x]=1;
    for(int i=head[x];i;i=ne[i])
    {
        int to=ver[i];
        if(to==fa)continue;
        dp(to,x);
        si[x]+=si[to];
        if(si[to]>si[maxsize[x]])maxsize[x]=to;
        int v;
        if(si[to]<=n/2)v=si[to];
        else v=d[to][0];
        if(d[x][0]<v)
        {
            d[x][1]=d[x][0];
            d[x][0]=v;
            pre[x]=to;
        }
        else if(d[x][1]<v)d[x][1]=v;
    }
}
void dfs(int x,int fa)
{
    ans[x]=1;
	if(si[maxsize[x]]>n/2) ans[x]=(si[maxsize[x]]-d[maxsize[x]][0]<=n/2);
	else if(n-si[x]>n/2) ans[x]=(n-si[x]-f[x]<=n/2);
	for(int i=head[x];i;i=ne[i])
    {
        int to=ver[i];
		if(to==fa) continue;
        int v;
		if(n-si[x]>n/2)v=f[x];
		else v=n-si[x];
		f[to]=max(f[to],v);
		if(pre[x]==to)f[to]=max(f[to],d[x][1]);
		else f[to]=max(f[to],d[x][0]);
		dfs(to,x);
	}
}
int main()
{
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    dp(1,0);
    dfs(1,0);
    for(int i=1;i<=n;i++)
        cout<<ans[i]<<" ";
    return 0;
}