#include "traffic.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<int> g[1000069];
ll w[1000069], sub[1000069], tot;
void dfs(int u, int p){
sub[u] = w[u];
for(int v : g[u]){
if(v == p) continue;
dfs(v,u);
sub[u] += sub[v];
}
}
int go(int u, int p){
for(int v : g[u]){
if(v == p) continue;
if(sub[v] > tot/2) return go(v,u);
}
if(tot - sub[u] > tot/2) return go(p,u);
return u;
}
int LocateCentre(int n, int pp[], int S[], int D[]){
tot = 0;
for(int i=0;i<n;i++){
w[i] = pp[i];
tot += w[i];
}
for(int i=0;i<n-1;i++){
g[S[i]].push_back(D[i]);
g[D[i]].push_back(S[i]);
}
dfs(0,-1);
return go(0,-1);
}
