#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pi pair<int, int>
#define f first
#define s second
const int mxN = 1e6+5;
const int mod = 1e9+7;
const int inf = 1e9;
vector<int> adj[mxN];
int res = 0, ans = 0, num = 2e9+5, f[mxN], traf[mxN], pos[mxN];
void dfs(int u, int e) {
for(int v : adj[u]) {
if(v == e) continue;
dfs(v, u);
traf[u] += traf[v];
pos[u] = max(pos[u], traf[v]);
}
pos[u] = max(pos[u], res-traf[u]-f[u]);
traf[u] += f[u];
}
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]);
f[i] = p[i];
res += p[i];
}
f[n-1] = p[n-1];
res += p[n-1];
dfs(0, -1);
for(int i = 0; i < n; i++) {
if(num > pos[i]) { num = pos[i]; ans = i; }
}
return ans;
}
