#include <bits/stdc++.h>
#include "traffic.h"
using namespace std;
const int mxN = 1000005;
vector<int> adj[mxN];
int sums[mxN], res[mxN];
void dfs(int u, int par, int p[]) {
sums[u] = p[u];
for(auto &v : adj[u]) {
if(v == par) continue;
dfs(v, u, p);
sums[u] += sums[v];
}
for(auto &v : adj[u]) {
if(v == par)
res[u] = max(res[u], sums[0]-sums[u]);
else
res[u] = max(res[u], sums[v]);
}
}
int LocateCentre(int n, int p[], int s[], int d[]) {
for(int i = 0; i < n-1; i++) {
adj[s[i]].push_back(d[i]);
adj[d[i]].push_back(s[i]);
}
dfs(0, -1, p);
int ans = INT_MAX, pos = 0;
for(int i = 0; i < n; i++) {
if(ans > res[i])
ans = res[i], pos = i;
}
return pos;
}
