贪心、树的重心--CF708C

本文主要是介绍贪心、树的重心--CF708C，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：
给定一棵n 个结点的树，对于每个结点求出它是否能通过至多一次操
作，使其成为这棵树的重心。一次操作可以删去原树中一条边，然后再
连上任意一条边，要求操作后图仍是一棵n 个结点的树

solution：
操作实际就是选择一个子树然后将其换个父亲
对于一个非重心结点u，它有且仅有一个儿子的子树大小大于n/2
贪心地从这个子树中找出一个尽量大且大小不超过n/2 的子树，使u成为它的新父亲
考虑原树的一个重心C，并将树以C 为根
对于非重心结点u，它父亲方向显然是超重的那个子树
重心的任意一个儿子大小均不超过n/2
重心下size 最大的子树中的结点，应把重心下次大子树接过去
其他子树中结点，应把重心下最大子树接过去
O(n)

这里要注意一些细节
比如以重心为根重新建树
还有就是找到最大和次大的子树怎么找
以及很重要的一点，如果最大的子树的siz=n/2的话
这种方法有可能失效
就比如说这组数据：
6
1 2
1 3
1 4
4 5
5 6
得出结果只有6不能，但实际上6也可以
因为这棵树不只有一个重心，这样子找出来重心可能有一个子树是链，比如1做根
这样子的话可能不对了，但旋转一下就可以发现以4做根的话
次大的子树大小就是3了，这样6就可行
所以说我们要特判一下如果mxson*2=n的话，所有重心上的节点都可行

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define maxn 400005
using namespace std;
int n,cnt,head[maxn],son[maxn],size=maxn,bary,t,premx,mxson,mx,pre;
bool can[maxn];inline int rd(){int x=0,f=1;char c=' ';while(c<'0' || c>'9') {if(c=='-')f=-1;c=getchar();}while(c<='9' && c>='0') x=x*10+c-'0',c=getchar();return x*f;
}struct EDGE {int to,nxt;}edge[maxn*2];void add(int x,int y){edge[++cnt].to=y;edge[cnt].nxt=head[x];head[x]=cnt;
}void dfs(int u,int fa){//找重心int tmp=0; son[u]=1;for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].to; if(v==fa) continue;dfs(v,u); son[u]+=son[v];tmp=max(tmp,son[v]);}tmp=max(tmp,n-son[u]);if(tmp<size || (tmp==size && u<bary)) size=tmp,bary=u;
}void find(int u){//找到最大和次大的子树要这么找for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].to;if(son[v]>mxson) mxson=son[v],mx=v;}for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].to;if(son[v]>premx && v!=mx) premx=son[v],pre=v;}
}void work(int u,int fa,bool b){if(b && mxson*2==n) can[u]=1;//这个地方一定要写！！！// if(b && n-premx-son[u]<=n/2) can[u]=1;//不同的写法，都可以if(b && son[u]+premx>(n-1)/2) can[u]=1;// else if(!b && son[u]+mxson>(n-1)/2) can[u]=1;else if(!b && n-mxson-son[u]<=n/2) can[u]=1;for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].to; if(v==fa) continue;work(v,u,b);}return ;
}int main(){n=rd();for(int i=1;i<n;i++) {int x=rd(),y=rd(); add(x,y); add(y,x);}dfs(1,0);if(bary!=1){memset(son,0,sizeof son); premx=mxson=0;t=bary;dfs(t,0); bary=t; //把重心转成根}can[bary]=1;find(bary);for(int i=head[bary];i;i=edge[i].nxt){int v=edge[i].to;if(v==mx) {work(v,bary,1);}else {work(v,bary,0);}}for(int i=1;i<=n;i++)if(can[i]) printf("1 ");else printf("0 ");return 0;
}

emmm
其实还有个做法是树形dp
思想也是一样的，但其实是没有想到以重心为根重建树的一种不好的做法
还是贪心清新多了
这里因为我懒就直接找了别人的代码···

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<stack>
#define INF 2100000000
#define ll long long
#define clr(x)  memset(x,0,sizeof(x))
#define clrmax(x)  memset(x,127,sizeof(x))using namespace std;inline int read()
{char c;int ret=0;while(!(c>='0'&&c<='9'))c=getchar();while(c>='0'&&c<='9'){ret=(c-'0')+(ret<<1)+(ret<<3);c=getchar();}return ret;
}#define M 400005int first[M],next[M*2],to[M*2];
int fa[M],size[M],can[M],c,n,t;
int fir[M],sec[M],fir_p[M];void addedge(int s,int v)
{next[++t]=first[s];first[s]=t;to[t]=v;
}void bulid(int x)
{size[x]=1;int b=1;for(int i=first[x];i;i=next[i]){int v=to[i];if(fa[x]==v)continue;fa[v]=x;bulid(v);if(size[v]<=n/2&&size[v]>fir[x]){fir[x]=size[v];fir_p[x]=v;}if(fir[v]>fir[x]){fir[x]=fir[v];fir_p[x]=v;}if(size[v]>n/2)b=0;size[x]+=size[v];}for(int i=first[x];i;i=next[i]){int v=to[i];if(v==fa[x]||v==fir_p[x])continue;if(size[v]<=n/2&&size[v]>sec[x])sec[x]=size[v];if(fir[v]>sec[x])sec[x]=fir[v];}if(b&&size[x]-1>=(n-1)/2)can[x]=1;if(size[x]>=n/2&&size[fir_p[x]]-fir[x]<=n/2)can[x]=1;
}void dfs(int x,int mx,int up)
{int te=mx;if(size[x]<=n/2&&(n-size[x]-mx)<=n/2)can[x]=1;for(int i=first[x];i;i=next[i]){mx=te;int v=to[i];if(v==fa[x])continue;int down=up+size[x]-size[v];if(down<=n/2)mx=max(mx,down);if(v==fir_p[x])mx=max(mx,sec[x]);else mx=max(mx,fir[x]);dfs(v,mx,down);}
}int main()
{freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);n=read();for(int i=1;i<n;i++){int a=read(),b=read();addedge(a,b);addedge(b,a);}bulid(1);dfs(1,0,0);for(int i=1;i<=n;i++)printf("%d ",can[i]);return 0;
}