#include "traffic.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e6;
const ll inf = 2e18;
int n, p[MAXN];
vector<int> adj[MAXN];
ll TOT;
ll stag[MAXN]; //#ppl that passes through the edge to my ancestor
ll max_st[MAXN]; //max(stag[i]), give i is my child
pair<int, int> ans = {inf, inf}; //{max #ppl in a road, the seed};
void dfs(int no, int anc){
for(int v : adj[no]) if(v != anc){
dfs(v, no);
stag[no] += stag[v];
max_st[no] = max(max_st[no], stag[v]);
}
stag[no] += p[no];
pair<int, int> ans_no = make_pair( max(TOT-stag[no], max_st[no]), no );
ans = min( ans, ans_no );
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
n = N;
for(int i = 0; i < N; i++) TOT += p[i]=pp[i];
for(int i = 0; i < N-1; i++){
adj[S[i]].push_back(D[i]);
adj[D[i]].push_back(S[i]);
}
dfs(0, 0);
return ans.second;
}
