Untitled
c_cpp
a month ago
670 B
5
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; }