Untitled

mail@pastecode.io avatar
unknown
c_cpp
a year ago
670 B
6
Indexable
Never
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
int sz[maxn] , n;
vector<int> adj[maxn];

void dfs(int u , int par){
	int w , mxx = -1; 
	for(auto v : adj[u]){
		if(v != par){
			dfs(v , u);
			sz[u] += sz[v];
			if(mxx < sz[v]) mxx = sz[v] , w = v;
		}
	}
	if(mxx > n/2){
		dfs(w , u);
	}
	else if(mxx != -1) cout << u +1  , exit(0);
}
int main(){
    int m;
    cin >> n;
    m = n - 1;
	for(int i = 0 ; i < n ; i++) sz[i] = 1;
    for(int i = 0 ; i < m ; i++){
        int u ,v;
        cin >> u >> v;
        --u;--v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
	dfs(0 , 0);
    return 0;
}