#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
const int N=1e6;
int sz[N];
int z[N];
vector<int> adj[N];
int a[N];
void dfs2(int u, int p, int out) {
if (p!=-1) z[p]=max(z[p],sz[u]);
for(auto&v:adj[u]) {
if (v==p) continue;
z[v]=max(z[v],sz[u]-sz[v]+out);
dfs2(v,u,sz[u]-sz[v]+out);
}
}
void dfs(int u, int p) {
sz[u]+=a[u];
for(auto&v:adj[u]) {
if (v==p) continue;
dfs(v,u);
sz[u]+=sz[v];
}
}
int LocateCentre(int n, int p[], int s[], int d[]) {
forn(i,n) a[i]=p[i];
forn(i,n-1) {
int u=s[i], v=d[i];
adj[u].pb(v);
adj[v].pb(u);
}
dfs(0,-1);
dfs2(0,-1,0);
int ans=0;
forn(i,n) if (z[i]<z[ans]) ans=i;
return ans;
}
