#include "traffic.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=1e6+50;
const ll inf=1e18;
vector<int>E[N];
int a[N],par[N],ind;
ll dp[N],dp1[N],sajz[N],res=inf;
void DFS1(int u,int parent){
par[u]=parent;
sajz[u]=a[u];
for(auto i:E[u]){
if(i==parent) continue;
DFS1(i,u);
sajz[u]+=sajz[i];
dp[u]+=dp[i]+sajz[i];
}
}
void DFS(int u){
int v=par[u];
if(u!=0) dp1[u]=dp1[v]+dp[v]-dp[u]-sajz[u]+sajz[0]-sajz[u];
if(res>dp[u]+dp1[u]) ind=u;
res=min(res,dp[u]+dp1[u]);
for(auto i:E[u]){
if(i==par[u]) continue;
DFS(i);
}
}
int LocateCentre(int n, int pp[], int S[], int D[]) {
for(int i=0;i<n;i++) a[i]=pp[i];
for(int i=0;i<n-1;i++){E[S[i]].pb(D[i]),E[D[i]].pb(S[i]);}
DFS1(0,-1);
DFS(0);
//for(int i=0;i<n;i++) {for(auto j:E[i]) printf("%i ",j);printf("\n");}
//for(int i=0;i<n;i++) printf("%i: %lld %lld %lld\n",i,dp[i],dp1[i],sajz[i]);
return ind;
}
