#include "traffic.h" #include<bits/stdc++.h> using namespace std; const int lim = 1e6 + 5; vector<int>g[lim]; int n, cnt[lim]; void dfs(int s, int p = -1){ for(int& d : g[s]){ if(d != p){ dfs(d, s); cnt[s] += cnt[d]; } } } int LocateCentre(int N, int pp[], int S[], int D[]){ n = N; for(int i = 0; i < n; i++){ cnt[i] = pp[i]; } for(int i = 0; i + 1 < n; i++){ g[S[i]].push_back(D[i]); g[D[i]].push_back(S[i]); } dfs(0); int s = 0, p = -1; while(true){ bool flag = true; for(int& d : g[s]){ if(d != p && cnt[d] > (cnt[0] >> 1)){ p = s; s = d; flag = false; break; } } if(flag){ break; } } return s; }