#include "traffic.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#define shit short int
#define ll long long
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<int, int>
#define NEK 1000000000000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize
#define prv1 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define sig 0.0000001
using namespace std;
vec<vec<ll>> g;
vec<ll> pod;
ll dfs(ll x, ll pr = -1) {
trav(i, g[x]) {
if (i == pr) continue;
pod[x] += dfs(i, x);
}
return pod[x];
}
ll mini = NEK;
ll minipoz = -1;
void dfs2(ll x, ll h = 0, ll pr = -1) {
ll mx = h;
trav(i, g[x]) {
if (i == pr) continue;
mx = max(mx, pod[i]);
dfs2(i, h + pod[x] - pod[i], x);
}
if (mx < mini) {
mini = mx;
minipoz = x;
}
return;
}
int LocateCentre(int n, int p[], int s[], int d[]) {
pod.resize(n, 0);
g.resize(n);
For(i, (n - 1)) {
g[s[i]].push_back(d[i]);
g[d[i]].push_back(s[i]);
}
For(i, n) {
pod[i] = p[i];
}
dfs(0);
dfs2(0);
return minipoz;
}
