#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int dp[N];
vector<int> ma[N];
void dfs(int x,int p=-1)
{
for(auto y:ma[x])
{
if(y!=p)
{
dfs(y,x);
dp[x]+=dp[y];
}
}
}
pair<int,int> bst={2e9,2e9};
void dfs_(int x,int p=-1)
{
int mx=0;
for(auto y:ma[x])mx=max(mx,dp[y]);
bst=min(bst,make_pair(mx,x));
for(auto y:ma[x])
{
if(y!=p)
{
dp[x]-=dp[y];
dp[y]+=dp[x];
dfs_(y,x);
dp[y]-=dp[x];
dp[x]+=dp[y];
}
}
}
int LocateCentre(int n, int pp[], int S[], int D[]) {
for(int i=0;i<n-1;i++)
{
ma[S[i]].push_back(D[i]);
ma[D[i]].push_back(S[i]);
}
for(int i=0;i<n;i++)
{
dp[i]=pp[i];
}
dfs(0);
bst=make_pair(2e9,2e9);
dfs_(0);
return bst.second;
}
