#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using pl = pair<long long, long long>;
using vi = vector<int>;
using vl = vector<long long>;
using vpi = vector<pair<int, int>>;
using vpl = vector<pair<long long, long long>>;
#define fur(i, a, b) for(ll i = a; i <= (ll)b; ++i)
#define ruf(i, a, b) for(ll i = a; i >= (ll)b; --i)
#define fr first
#define sc second
#define mp make_pair
#define pb emplace_back
#define nl "\n"
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
const ll inf = 2e9L + 5;
void st_evth(ll cur, ll src, vl &cnt, vl &cong, int pp[], vl adj[]) {
cnt[cur] = pp[cur];
cong[cur] = 0;
for(auto u : adj[cur]) {
if(u != src) {
st_evth(u, cur, cnt, cong, pp, adj);
cnt[cur] += cnt[u];
cong[cur] = max(cong[cur], cnt[u]);
}
}
}
void dfs(ll cur, ll src, vl &cnt, vl &cong, int pp[], vl adj[], vl &ans) {
ll opt = 0;
for(auto u : adj[cur]) {
if(u != src) {
opt = max(opt, cnt[u]);
} else {
opt = max(opt, cnt[0] - cnt[cur]);
}
}
ans[cur] = opt;
for(auto u : adj[cur]) {
if(u != src) {
dfs(u, cur, cnt, cong, pp, adj, ans);
}
}
}
int LocateCentre(int n, int pp[], int S[], int D[]) {
vl adj[n];
fur(i, 0, n - 2) {
adj[S[i]].pb(D[i]);
adj[D[i]].pb(S[i]);
}
vl cnt(n);
vl cong(n);
st_evth(0, -1, cnt, cong, pp, adj);
vl ans(n);
dfs(0, -1, cnt, cong, pp, adj, ans);
pl best = {inf, -1};
fur(i, 0, n - 1) {
best = min(best, {ans[i], i});
}
return best.sc;
}
