#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int>pii;
vector<int>adj[1000005];
int arr[1000005];
int d[1000005];
int storage[1000005];
int sz[1000005];
void dfs(int index, int par){
sz[index]=arr[index];
storage[index]=arr[index]*d[index];
for(auto it:adj[index]){
if(it==par) continue;
d[it]=d[index]+1;
dfs(it,index);
sz[index]+=sz[it];
storage[index]+=storage[it];
}
}
int best=LONG_LONG_MAX;
int cur=0;
void dp(int index, int par, int val){
if(storage[0]+val<best){
best=storage[0]+val;
cur=index;
}
for(auto it:adj[index]){
if(it==par) continue;
int next=sz[0]-2*sz[it]+val;
dp(it,index,next);
}
}
int32_t LocateCentre(int32_t N, int32_t pp[], int32_t S[], int32_t D[]) {
for(int x=0;x<N-1;x++){
adj[S[x]].push_back(D[x]);
adj[D[x]].push_back(S[x]);
}
for(int x=0;x<N;x++) arr[x]=pp[x];
dfs(0,-1);
dp(0,-1,0);
return cur;
}
