蒟蒻求hack
  • 板块P1395 会议
  • 楼主NOIPer40
  • 当前回复5
  • 已保存回复5
  • 发布时间2020/12/3 16:20
  • 上次更新2023/11/5 06:48:48
查看原帖
蒟蒻求hack
185026
NOIPer40楼主2020/12/3 16:20
#include<cstdio>
#define maxn 50010
#define maxm 100010
using namespace std;
int n,head[maxn],nxt[maxm],to[maxm],cnt,dep[maxn]={-1},s,f[maxn],size[maxn],g[maxn]={1e9},ans;
void con(int u,int v){
	nxt[++cnt]=head[u];
	to[cnt]=v;
	head[u]=cnt;
}
void add(int a,int b){
	con(a,b);
	con(b,a);
}
void dfs(int x,int fa){
	f[x]=dep[x]=dep[fa]+1;
	size[x]=1;
	s+=dep[x];
	for(int i=head[x];i;i=nxt[i]){
		int ti=to[i];
		if(ti!=fa){
			dfs(ti,x);
			f[x]+=f[ti];
			size[x]+=size[ti];
		}
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b);
	}
	dfs(1,0);
	for(int i=1;i<=n;i++){
		g[i]=s+(n-2*size[i])*dep[i];
		if(g[i]<g[ans])
			ans=i;
	}
	printf("%d %d",ans,g[ans]);
	return 0;
}
2020/12/3 16:20
加载中...