#include<bits/stdc++.h>
#include "traffic.h"
using namespace std;
#define ll long long
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back
const int MAXN=1e6+10;
ll dp[MAXN],pai[MAXN];
vector<int> g[MAXN];
int LocateCentre(int n, int v[], int S[], int D[]) {
fall(i,0,n-2){
int a=S[i],b=D[i];
g[a].pb(b),g[b].pb(a);
}
auto dfs=[&](auto dfs,int x,int p) ->void {
dp[x]=v[x];
pai[x]=p;
for(auto u:g[x]) if(u!=p) dfs(dfs,u,x),dp[x]+=dp[u];
};
dfs(dfs,0,-1);
ll mn=1e15,ans=-1;
fall(i,0,n-1){
ll cur=dp[0]-dp[i];
for(auto u:g[i]) if(u!=pai[i]) cur=max(cur,dp[u]);
if(mn>cur) mn=cur,ans=i;
}
return ans;
}
