Demo entry 6713883

的味道

   

Submitted by 非让我乳房的 on Feb 10, 2018 at 14:29
Language: C++. Code size: 933 Bytes.

//树的重心.cpp
#include<bits/stdc++.h>
const int N=1000010;
const int inf=0x7f7f7f7f;
using namespace std;
int f[N],size[N],n,head[N],tot;
int rt,sum;
struct Edge{int u,v,next;}G[N<<1];
inline void addedge(int u,int v){
	G[++tot].u=u;G[tot].v=v;G[tot].next=head[u];head[u]=tot;
	G[++tot].u=v;G[tot].v=u;G[tot].next=head[v];head[v]=tot;
}
inline void getrt(int u,int fa){
	size[u]=1;f[u]=0;
	for(int i=head[u];i;i=G[i].next){
		int v=G[i].v;if(v==fa)continue;
		getrt(v,u);
		size[u]+=size[v];
		f[u]=max(f[u],size[v]);
	}
	f[u]=max(f[u],sum-size[u]);
	if(f[u]<f[rt])rt=u;
}
inline int read(){
	int f=1,x=0;char ch;
	do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
	do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
	return f*x;
}
int main(){
	n=read();
	for(int i=1;i<n;i++){
		int u=read(),v=read();
		addedge(u,v);
	}
	rt=0;sum=n;f[0]=inf;getrt(1,0);
	printf("%d\n",rt);
	return 0;
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).