#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define all(v) v.begin(), v.end()
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx2")
int sm = 0;
vector<vector<int>> adj;
vector<int> sz;
vector<int> dp;
int dfs(int a, int p) {
dp[a] = sz[a];
for (auto &b : adj[a]) {
if(b == p) continue;
dp[a] += dfs(b, a);
}
return dp[a];
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
sz.assign(pp, pp + N);
adj.assign(N, {});
dp.assign(N, 0);
for (auto i : sz) sm += i;
for (int i = 0; i < N - 1; i++) {
adj[S[i]].push_back(D[i]);
adj[D[i]].push_back(S[i]);
}
dfs(0, 0);
int mn = INT_MAX;
int mnc = 0;
for (int i = 0; i < N; i++) {
int m = 0;
int s = sz[i];
for (auto &b : adj[i]) {
if(dp[b] < dp[i]){
m = max(m, dp[b]);
s += dp[b];
}
}
m = max(m, sm - s);
if(m < mn){
mn = m;
mnc = i;
}
}
return mnc;
}
