#include <bits/stdc++.h>
#include "traffic.h"
using namespace std;
constexpr int NMAX = 1e6 + 5;
vector <int> G[NMAX];
int valMax[NMAX];
int sp[NMAX];
int Max[NMAX];
int Dad[NMAX];
void Dfs (int Node, int dad = -1) {
Dad[Node] = dad;
for (auto it : G[Node]) {
if (it == dad) continue;
Dfs(it, Node);
sp[Node] += sp[it];
Max[Node] = max(Max[Node], sp[it]);
}
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
int Total = 0;
for (int i = 0; i < N; ++ i ) {
sp[i] = pp[i];
Total += pp[i];
}
for (int i = 0; i < N-1; ++ i ) {
G[S[i]].push_back(D[i]);
G[D[i]].push_back(S[i]);
}
Dfs(0);
int Min = Total+1;
int poz = -1;
for (int i = 0; i < N; ++ i ) {
int val = Max[i];
val = max(val, Total - sp[i]);
if (val < Min) {
Min = val;
poz = i;
}
}
return poz;
}
