求调,76'
查看原帖
求调,76'
1015715
H_F_X_楼主2024/12/7 15:42
#include<algorithm>
#include<iostream>
#include<climits>
#include<cstring>
#include<iomanip>
#include<utility>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<deque>
#include<queue>
#include<stack>
#include<list>
#include<map>
#include<set>
#define RI register int
#define RC register char
using namespace std;
int n,x,y,sum[100010],q;
vector<int> v[100010],s[100010]; 
inline int read() {
	RI x=0, w=0;
	RC ch=0;
	while(!isdigit(ch)){
		w|=ch=='-',ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
	}
	return w?-x:x;
}
void dfs(int u,int fa){
	sum[u]=1;
	for(int i=0;i<v[u].size();i++){
		if(v[u][i]==fa){
			continue;
		}
		dfs(v[u][i],u);
		s[u].push_back(v[u][i]);
		sum[u]+=sum[v[u][i]];
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1,-1);
	for(int i=1;i<=n;i++){
		bool f=1;
		for(int j=0;j<s[i].size();j++){
			int u=s[i][j];
			if(sum[u]>n/2){
				f=0;
				break;
			}
		}
		if(sum[i]>=n/2&&f){
			cout<<i<<endl;
			q=0;
		}
	}
	if(q){
		puts("NONE");
	}
	return 0;
}
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
//	fclose(stdin);
//	fclose(stdout);

2024/12/7 15:42
加载中...