#include "traffic.h"
#include <vector>
#include <algorithm>
#include <cstring>
#define ll long long
#define MAX 1000000
using namespace std;
ll n;
vector<vector<ll>> adj_list(MAX, vector<ll>{});
ll vals[MAX];
ll dp[MAX];
void dfs_cnt(ll idx, ll parent = -1) {
dp[idx] = vals[idx];
for (auto &each: adj_list[idx]) {
if (each == parent) continue;
dfs_cnt(each, idx);
dp[idx] += dp[each];
}
}
ll mx(vector<ll> tc) {
ll ret = 0;
for (auto &each: tc) ret = max(ret, each);
return ret;
}
ll calc(ll idx) {
vector<ll> ret;
for (auto &each: adj_list[idx]) ret.push_back(dp[each]);
return mx(ret);
}
/* cnt, node */
pair<ll, ll> foo(ll idx, ll parent = -1) {
pair<ll, ll> ret = {calc(idx), idx};
for (auto &each: adj_list[idx]) {
if (each == parent) continue;
dp[idx] -= dp[each];
dp[each] += dp[idx];
pair<ll, ll> pos = foo(each, idx);
if (pos.first < ret.first) ret = pos;
dp[each] -= dp[idx];
dp[idx] += dp[each];
}
return ret;
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
n = (ll)N;
for (ll i = 0; i < n; ++i) vals[i] = (ll)pp[i];
for (ll i = 0; i < (n - 1); ++i) {
ll x = S[i], y = D[i];
adj_list[x].push_back(y);
adj_list[y].push_back(x);
}
memset(dp, 0, sizeof dp);
dfs_cnt(0);
pair<ll, ll> ans = foo(0);
return ans.second;
}
