题解 CF708C 【Centroids】
LeavingZ
2020-08-01 19:33:17
# $\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}$
谢谢管理大大审核^_^