/*
Zadanie: Traffic
Autor: Tomasz Kwiatkowski
*/
#include <bits/stdc++.h>
#include "traffic.h"
#define pb push_back
using namespace std;
const int MAXN = 1e6 + 7;
vector<int> G[MAXN];
int dp[MAXN];
void DFS_dp(int v, int p)
{
for (auto u : G[v]) {
if (u != p) {
DFS_dp(u, v);
dp[v] += dp[u];
}
}
}
pair<int, int> DFS_move(int v, int p)
{
pair<int, int> best = {0, 0};
for (auto u : G[v])
best = max(make_pair(dp[u], v), best);
for (auto u : G[v]) {
if (u != p) {
dp[v] -= dp[u];
dp[u] += dp[v];
best = min(DFS_move(u, v), best);
dp[u] -= dp[v];
dp[v] += dp[u];
}
}
return best;
}
int LocateCentre(int N, int P[], int S[], int D[])
{
for (int i = 0; i < N-1; ++i)
G[S[i]].pb(D[i]), G[D[i]].pb(S[i]);
for (int i = 0; i < N; ++i)
dp[i] = P[i];
DFS_dp(0, 0);
return DFS_move(0, 0).second;
}
