#include <bits/stdc++.h>
using namespace std;
#include "traffic.h"
//#define int long long
typedef long long ll;
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll P[1000005], sz[1000005];
vector <int> adj[1000005];
pair<long long, int> ans = {1e18, 0};
ll sm;
void dfs(int x, int par){
sz[x] = P[x];
ll tmp = 0;
for(auto i : adj[x]){
if(i == par)continue;
dfs(i, x);
sz[x] += sz[i];
tmp = max(tmp, sz[i]);
}
tmp = max(tmp, sm - sz[x]);
ans = min(ans, {tmp, x});
}
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++)P[i] = pp[i], sm += pp[i];
dfs(0, -1);
return ans.se;
}
