求大佬们的检查,谢谢
  • 板块P1395 会议
  • 楼主hezhenzhang
  • 当前回复2
  • 已保存回复2
  • 发布时间2020/10/7 21:39
  • 上次更新2023/11/5 11:38:45
查看原帖
求大佬们的检查,谢谢
365248
hezhenzhang楼主2020/10/7 21:39
#include<bits/stdc++.h>
using namespace std;
const int maxn=50004;

int fi[maxn],to[maxn*2],ne[maxn*2],si[maxn],fa[maxn],dep[maxn],tot,n;
inline void add(int x,int y){
	to[++tot]=y;ne[tot]=fi[x];fi[x]=tot;
}

inline int dfs(int x,int fath){
	si[x]=1;fa[x]=fath;dep[x]=dep[fath]+1;//标准 
	for(int i=fi[x];i;i=ne[i]){
		if(to[i]!=fath){
			si[x]+=dfs(to[i],x);
		}
	}
	return si[x];
}

inline bool check(int x){
	if(n-si[x]>n/2) return 0;
	for(int i=fi[x];i;i=ne[i]){
		if(fa[to[i]]==x && si[to[i]]>n/2) return 0;
	}
	return 1;
}

inline void dfs2(int x,int fath){
	dep[x]=dep[fath]+1;//标准 
	for(int i=fi[x];i;i=ne[i]){
		if(to[i]!=fath){
			dfs(to[i],x);
		}
	}
}

int main(){
	cin>>n;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	dfs(1,0);
	for(int i=1;i<=n;i++){
		if(check(i)){
			memset(dep,0,sizeof dep);
			int ans;
			dfs2(i,0);//以重心为根遍历
			for(int i=1;i<=n;i++){
				ans+=dep[i]-1;
			} 
			cout<<i<<" "<<ans;
			return 0;
		}
	}
	return 0;
}
2020/10/7 21:39
加载中...