Untitled

mail@pastecode.io avatarunknown
c_cpp
a month ago
1.1 kB
2
Indexable
Never
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
using namespace std;
const int maxn = 1e5;
int sz[maxn] , a[maxn] , nw;
bool mark[maxn];
vector<int> adj[maxn];

void dfs(int u){
    mark[u] = true;
	sz[u] = 1;
    for(auto v : adj[u]){
        if(!mark[v]){
			dfs(v);
            sz[u] += sz[v];
        }
    }
}
void bfs(int u){
	mark[u] = true;
	queue<int> q;
	q.push(u);
	while(!q.empty()){
		int v = q.front();
		q.pop();
		for(auto w : adj[v]){
			if(!mark[w]){
				mark[w] = true;
				q.push(w);
				a[v] = max(sz[w] , a[v]);
				//cout << a[v] << ' ';
			}
		}
		a[v] = max(sz[nw]-sz[v] , a[v]);
		if(a[v] <= (sz[nw]/2)){
			cout << v+1 << '\n';
			exit(0);
		}
	}
}
int main(){
	ios;
    int n , m;
    cin >> n;
    m = n-1;
    for(int i = 0 ; i < m ; i++){
        int u , v;
        cin >> u >> v;
        --u;--v;
		if(i == 0) nw = u;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
	dfs(nw);
	memset(mark , 0 , sizeof mark);
	bfs(nw);
    return 0;
}