#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#define LOG(...) cerr << "[" << #__VA_ARGS__ << "]: " << repr(__VA_ARGS__) << endl;
#define MSG(args) cerr << args << "\n";
#define debug(x) x
#else
#define LOG(...)
#define MSG(args)
#define debug(x)
#endif
#define mp make_pair
#define pb push_back
#define sz(x) (int)((x).size())
#define ms(x, v) memset((x), v, sizeof(x))
#define all(x) (x).begin(), (x).end()
#define REP(x, n) for(int x = 0; x < n; x++)
#define REPV(x, v, n) for(int x = v; x < n; x++)
#define REVE(x, n) for(int x = n; x >= 0; x--)
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vii = vector<pii>;
using vvi = vector<vi>;
vi adj[1000010];
ll tot_fans = 0, sze[1000010], cnt[1000010];
void dfs(int u, int parent, int P[])
{
for(int v : adj[u]) if(v != parent)
{
dfs(v, u, P);
sze[u] += sze[v];
cnt[u] = max(cnt[u], sze[v]);
}
cnt[u] = max(cnt[u], tot_fans - sze[u] - P[u]);
sze[u] += P[u];
}
int LocateCentre(int N, int P[], int S[], int D[])
{
tot_fans = accumulate(P, P + N, 0LL);
REP(i, N - 1)
adj[S[i]].pb(D[i]), adj[D[i]].pb(S[i]);
dfs(0, -1, P);
return min_element(cnt, cnt + N) - cnt;
}
