#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
vector<int> con[MAXN];
int p[MAXN];
int n, res = INT_MAX, best = -1;
int total = 0;
int find(int i, int par)
{
int sum = 0, most = 0;
for (auto j : con[i])
{
if (j == par)
continue;
int r = find(j, i);
sum += r, most = max(most, r);
}
sum += p[i];
most = max(most, total - sum);
if (most < res)
best = i, res = most;
return sum;
}
int LocateCentre(int N, int P[], int S[], int D[])
{
n = N;
for (int i = 0; i < n - 1; i++)
con[S[i]].push_back(D[i]), con[D[i]].push_back(S[i]);
for (int i = 0; i < n; i++)
total += P[i], p[i] = P[i];
find(0, 0);
return best;
}
