Untitled
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; }