#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#include "traffic.h"
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define INF 1'000'000'050
#define pb push_back
int n;
int W[1'000'050];
vi E[1'000'050];
int sz[1'000'050];
int num = 0;
int dfs(int at, int p) {
if (sz[at] != -1) return sz[at];
int tot = W[at];
// cout << "ello " << at << " " << p << endl;
for (auto e : E[at]) {
// cout << "ello" << endl;
if (e != p) tot += dfs(e, at);
}
return sz[at] = tot;
}
ii dfs2(int at, int p) {
int m = 0;
int tot = 0;
ii bst = {INF, -1};
for (auto e : E[at]) {
if (e != p) {
m = max(m, sz[e]);
tot += sz[e];
bst = min(bst, dfs2(e, at));
}
}
m = max(m, num - W[at] - tot);
bst = min(bst, {m, at});
return bst;
}
int LocateCentre(int N, int P[], int S[], int D[]) {
memset(sz, -1, sizeof(sz));
// cout << "----" << endl;
n = N;
rep(i, 0, n) { num += W[i] = P[i]; }
rep(i, 0, n - 1) {
E[S[i]].pb(D[i]);
E[D[i]].pb(S[i]);
}
dfs(0, -1);
// rep(i, 0, n) cout << sz[i] << endl;
int ans = dfs2(0, -1).second;
// cout << "---" << endl;
return ans;
}
