#include "traffic.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>v[1000005];
int cost[1000005];
int mxc[1000005];
int ppl[1000005];
void dfs(int u,int p=-1){
//cerr<<u<<"\n";
for(auto x:v[u])if(x!=p){
dfs(x,u);
cost[u]+=cost[x]+ppl[x];
mxc[u]=max(cost[x]+ppl[x],mxc[u]);
}
}
int centroid(int u,int val=0,int p=-1){
//cerr<<u<<" "<<val<<"\n";
int sum=val;
for(auto x:v[u])if(x!=p)sum+=cost[x]+ppl[x];
//for(auto x:v[u])if(x!=p)cerr<<cost[x]<<" "<<ppl[x]<<"\n";
//cerr<<sum<<"\n";
for(auto x:v[u])if(x!=p){
if(max(val,mxc[u])>max(sum-cost[x]-ppl[x]+ppl[u],mxc[x]))return centroid(x,sum-cost[x]-ppl[x]+ppl[u],u);
}
return u;
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
for(int i=0;i<N;i++)ppl[i]=pp[i];
for(int i=0;i<N-1;i++)v[S[i]].push_back(D[i]),v[D[i]].push_back(S[i]);
dfs(0);
//for(int i=0;i<N;i++)cerr<<cost[i]<<"\n";
return centroid(0);
}
