#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 1e5 + 10;
const ll INF = 1e18;
int cnt[MAXN], sub[MAXN];
ll dp_1[MAXN], dp_2[MAXN];
vector<int> adj[MAXN];
void dfs_1(int v, int p){
sub[v] = cnt[v];
for(auto u : adj[v]){
if(u != p){
dfs_1(u, v);
sub[v] += sub[u];
dp_1[v] += dp_1[u];
}
}
dp_1[v] += sub[v] - cnt[v];
}
void dfs_2(int v, int p, int n){
for(auto u : adj[v]){
if(u != p){
dp_2[u] = dp_2[v] + dp_1[v] - dp_1[u] + sub[1] - 2 * sub[u];
dfs_2(u, v, n);
}
}
}
int LocateCentre(int n, int p[], int s[], int d[]){
for(int i=0; i<n; i++) cnt[i + 1] = p[i];
for(int i=0; i<(n - 1); i++){
adj[s[i] + 1].push_back(d[i] + 1);
adj[d[i] + 1].push_back(s[i] + 1);
}
dfs_1(1, 1);
dfs_2(1, 1, n);
pair<ll, int> ans = {INF, -1};
for(int i=1; i<=n; i++) ans = min(ans, {dp_1[i] + dp_2[i], i});
return ans.second - 1;
}
