#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()
#define INF 1000000000
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;
vi graph[1000005];
vii traffic;
int subs[1000005], pop[1000005], best = 2 * INF + 1, ans;
bitset<1000005> vis;
void getsubs(int u)
{
vis[u] = 1;
int s = 0;
trav(v, graph[u])
{
if (vis[v])
continue;
getsubs(v);
s += subs[v] + pop[v];
}
subs[u] = s;
}
void solve(int u, int over)
{
vis[u] = 1;
traffic.clear();
if (!graph[u].size() || (graph[u].size() == 1 && vis[graph[u][0]]))
{
if (over < best)
best = over, ans = u;
return;
}
trav(v, graph[u])
{
if (vis[v])
continue;
traffic.emplace_back(subs[v] + pop[v], v);
}
sort(traffic.begin(), traffic.end(), greater<>());
if (max(traffic[0].first, over) < best)
{
best = max(traffic[0].first, over);
ans = u;
}
over += pop[u];
rep(i, 1, (int)traffic.size())
over += traffic[i].first;
solve(traffic[0].second, over);
}
int LocateCentre(int n, int p[], int s[], int d[])
{
fill(graph, graph + 1000000, vi());
rep(i, 0, n) pop[i] = p[i];
rep(i, 0, n - 1)
{
graph[s[i]].push_back(d[i]);
graph[d[i]].push_back(s[i]);
}
vis.reset();
getsubs(0);
vis.reset();
solve(0, 0);
return ans;
}
