[CF708C]Centroids
发布时间:2020-12-16 09:12:43 所属栏目:百科 来源:网络整理
导读:Centroids 题目大意 一棵树,对于每个点,我们删掉任意一条边,再连上任意一条边,求这样操作后可以使这个点为重心的点数 范围 (n) 级别 Solution 嗯,首先对于一个点 (u) ,若全部子树(包括自己头上的那一堆)都不到总点数 (n) 的一半的肯定符合条件
Centroids题目大意一棵树,对于每个点,我们删掉任意一条边,再连上任意一条边,求这样操作后可以使这个点为重心的点数 范围(n)级别 Solution嗯,首先对于一个点(u),若全部子树(包括自己头上的那一堆)都不到总点数(n)的一半的肯定符合条件 然后若(u)的子树({ v })中有一个点数(> {n over 2})的(v1),我们要在这样的子树中找到最大的一棵点数(<= {n over 2})的子树 (v2)。 把它断开来,然后把(v2)连上(u),如果这样后(v1)点数(<= {n over 2}),就满足条件 然后用树形DP的老思想:先处理出子树的,再利用子树信息搞一搞头上的就可以了。 code: #include<bits/stdc++.h> using namespace std; struct qwq{ int v; int nxt; }edge[800010]; int cnt=-1; int head[400010]; void add(int u,int v){ edge[++cnt].nxt=head[u]; edge[cnt].v=v; head[u]=cnt; } int fir[400010],sec[400010]; void up_max(int &x,int &y,int val){ if(val>x){y=x;x=val;return;} else if(val>y){y=val;return;} else return; } int n; int siz[400010]; int usiz[400010]; int g[400010]; void dfs(int u,int fa){ siz[u]=1; for(int i=head[u];~i;i=edge[i].nxt){ int v=edge[i].v; if(v==fa)continue; dfs(v,u); siz[u]+=siz[v]; if(siz[v]>n/2)g[u]=v; if(siz[v]<=n/2)up_max(fir[u],sec[u],siz[v]); else up_max(fir[u],fir[v]); } usiz[u]=n-siz[u]; if(usiz[u]>n/2)g[u]=-1; } int um[400010]; void dfs2(int u,int fa){ if(usiz[u]<=n/2){ um[u]=usiz[u]; } else if(fir[fa]==siz[u]){ um[u]=max(um[fa],sec[u]); } else { um[u]=max(um[fa],fir[fa]); } for(int i=head[u];~i;i=edge[i].nxt){ int v=edge[i].v; if(v==fa)continue; dfs2(v,u); } } bool ans[400010]; int main(){ memset(head,-1,sizeof(head)); scanf("%d",&n); for(int i=1;i<n;++i){ int u,v; scanf("%d%d",&u,&v); add(u,v),add(v,u); } dfs(1,0); dfs2(1,0); for(int i=1;i<=n;++i){ if((!g[i])||(g[i]==-1&&usiz[i]-um[i]<=n/2)||(g[i]!=-1&&siz[g[i]]-fir[g[i]]<=n/2))ans[i]=true; } for(int i=1;i<=n;++i){ printf("%d ",ans[i]); } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |