#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX_N = 1e6 + 1;
vector<int> adj[MAX_N];
int sz[MAX_N];
int par[MAX_N];
void dfs(int here, int parent = -1) {
par[here] = parent;
for (int there: adj[here]) {
if (there != parent) {
dfs(there, here);
sz[here] += sz[there];
}
}
}
int LocateCentre(int n, int pp[], 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]);
}
for (int i=0; i<n; ++i) sz[i] = pp[i];
dfs(0);
int tot_sz = 0;
int ans = 2e9 + 2;
int location = -1;
for (int i=0; i<n; ++i) tot_sz += pp[i];
for (int i=0; i<n; ++i) {
int max_congestion = 0;
for (int there: adj[i]) {
if (there == par[i]) {
max_congestion = max(max_congestion, tot_sz - sz[i]);
} else {
max_congestion = max(max_congestion, sz[there]);
}
}
if (ans > max_congestion) {
ans = max_congestion;
location = i;
}
}
return location;
}
