CF708C Centroids(树形dp)

Centroids - 洛谷https://www.luogu.com.cn/problem/CF708C这是一道cf2300的树形dp题,个人感觉十分妙,所以特此写题解记录一下好题.

思路:针对于这个重心的定义,我们进行分情况讨论(设dfs我们当前遍历的点为x,发亲节点为fa):

首先可以确定的一件事是,在这整棵树里面,我们选定一个点时,肯定只会有一颗子树的大小>=n/2.所以我们只需要考虑砍哪一颗即可.分情况讨论:

1.当x的所有子树的大小都<=n/2并且n减去包含x这棵子树之后剩下的大小(这个大小其实是如果我们认定x为根节点的另一棵子树的大小)也是<=n/2的那么这个点肯定可以作为重心.

2.当x的某棵子树大小>n/2,那么我们就要考虑减去这棵子树中最大的<=n/2的子树之后这棵子树的大小<=n/2那么肯定也是成立的,反之即使减去了最大的<=n/2的子树还是不符合条件就肯定不成立(ps:这棵被减去的小子树被插到了x的下方成为了一颗新的x的子树.).为了实现这个判断,我们考虑维护一个f[x],f[x]=max(f[y],siz[x]).y是x的子节点,满足之前的都<=n/2的情况.

3.第三种情况就有点难处理了.我们知道如果以x为重心也就是考虑它为根节点,那么在现实情况的子树意外,它的现实情况的父亲节点的上方是x为重心时候的子树.所以我们考虑x的上方踩在>n/2的子树的情况,和第二种情况类似.但是有一个问题.我们无法位数出上方的f[fa].但是我们可以维护出每个点的f的次大和最大值f[x][0/1].这样的话假设x所在的fa的子树时如果f值大于区域子树,我们就可以取次大值f[x][1]作为"最大值"进行类似于情况2的判断.当x所在的子树大小不是最大的时,我们只需要考虑f[x][0]最大值即可.

针对这上述情况判断即可

下面上代码,有注释:

#include
using namespace std;
const int N=4e5+10,mod=998244353;
int h[N],n,ans[N],f[N][3],siz[N],maxson[N],maxpos[N],selectmax[N],tot=0;
/*
f[x][0/1]维护的是x的子树中次大和最大的大小<=n/2的子树的大小maxpos维护的是x的最大值是哪一个儿子maxson维护的是针对于这个点我们切除的最大的<=n/2的树的大小selectmax是方便判断,当x上方的父亲节点所在的树索要切割的
"最大"的最大子树的是哪个.如果最大是x所在的树我们就算则次大值判断
反之选最大值判断
*/
struct node
{int to,ne;
}edge[2*N];
void add(int x,int y)
{edge[++tot].to=y;edge[tot].ne=h[x];h[x]=tot;return ;
}
void dfs1(int x,int fa)
{maxpos[0]=0;f[x][0]=f[x][1]=1;siz[x]=1;//初始化for(int i=h[x];i!=-1;i=edge[i].ne){int y=edge[i].to;if(y==fa)continue;dfs1(y,x);siz[x]+=siz[y];int v;if(siz[y]>siz[maxpos[x]])maxpos[x]=y;//记录最大的儿子if(siz[y]<=n/2)v=siz[y];else if(f[y][0]<=n/2)v=f[y][0];if(v>=f[x][0]){selectmax[x]=y;//记录我们所选的f的最大是谁f[x][1]=f[x][0];f[x][0]=v;}else if(v>=f[x][1])f[x][1]=v;//更新最大次大值}return ;
}
void dfs2(int x,int fa)
{ans[x]=1;if(siz[x]>n/2&&siz[maxpos[x]]-f[maxpos[x]][0]>n/2)ans[x]=0;//此处判断的是siz[x]>n/2所以我们从x的子树中切除某棵子树的情况//我们减去最大儿子的某棵子树,只要减去之后剩下的权重>n/2就不成立else if(siz[x]<=n/2&&n-siz[x]-maxson[x]>n/2)//此处判断的是siz[x]<=n/2所以我们从x的上方fa切除某棵子树(不包括含x的子树)//当减去了含x子树和上方的需要减去的子树剩下的树权重>n/2就不成立ans[x]=0;for(int i=h[x];i!=-1;i=edge[i].ne){int y=edge[i].to,num;if(y==fa)continue;if(n-siz[x]>n/2) num=maxson[x];else num=n-siz[x];maxson[y]=max(maxson[y],num);//更新最大剪去数值的大小if(selectmax[x]==y)maxson[y]=max(maxson[y],f[x][1]);//当fa的最大的f的值是当前这个子节点,那么要去次大值,因为最大值不能包含这个点elsemaxson[y]=max(maxson[y],f[x][0]);//反之,这个点可以选,直接去最大值即可dfs2(y,x);}return ;
}
void solve()
{int x,y;memset(h,-1,sizeof h);cin>>n;for(int i=1;i>x>>y;add(x,y);add(y,x);}dfs1(1,0);dfs2(1,0);for(int i=1;i<=n;i++)cout<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！