#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
#define ar array
#define ll long long
const int mxn = 2e6 + 20;
vector<int> g[mxn];
int sz[mxn], dp[mxn], A[mxn], ans[mxn];
void dfs1(int x,int p){
sz[x] = A[x];
dp[x] = 0;
for(auto u: g[x]){
if(u == p)continue;
dfs1(u, x);
sz[x] += sz[u];
dp[x] = max(dp[x], sz[u]);
}
}
void dfs2(int x,int p){
ans[x] = dp[x];
for(auto u: g[x]){
if(u == p)continue;
int osx = sz[x];
int osu = sz[u];
int odx = dp[x];
int odu = dp[u];
sz[x] -= sz[u];
sz[u] += sz[x];
dp[u] = max(dp[u], sz[x]);
dfs2(u, x);
sz[x] = osx;
sz[u] = osu;
dp[x] = odx;
dp[u] = odu;
}
}
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++){
g[S[i]].push_back(D[i]);
g[D[i]].push_back(S[i]);
}
dfs1(0, 0);
dfs2(0, 0);
int mi = 0;
for(int i =1;i<n;i++){
if(ans[i] < ans[mi])mi = i;
}
return mi;
}
