#include "traffic.h"
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pii pair<ll, ll>
const ll mod = 1e9 + 7;
const ll mxN = 1e6 + 5;
using namespace std;
vector<vector<int>>v;
int dpD[mxN],dpU[mxN], ans[mxN];
int val[mxN];
void dfs(int u,int par){
dpD[u] = val[u];
for(auto x : v[u]){
if(x == par) continue;
dfs(x,u);
ans[u] = max(ans[u],dpD[x]);
dpD[u] += dpD[x];
}
}
void hfs(int u,int par){
if(par != -1){
dpU[u] = dpU[par] + dpD[par] - dpD[u];
ans[u] = max(ans[u],dpU[u]);
}
for(auto x : v[u]){
if(x == par) continue;
hfs(x,u);
}
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
v.resize(N + 3);
for(int i = 0;i < N;i++){
val[i] = pp[i];
if(i == N - 1) continue;
v[S[i]].push_back(D[i]);
v[D[i]].push_back(S[i]);
}
int mn = INT_MAX,mxid = -1;
dfs(0,-1);
hfs(0,-1);
for (int i = 0; i < N; i++)
{
if(ans[i] < mn){
mn = ans[i];
mxid = i;
}
}
return mxid;
}
