//HEADER
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
typedef long long ll;
typedef pair<int, int> pii;
vector<vector<int>> adj(1e6+5);
// congestion passing through each city
vector<int> cong(1e6+5);
int minCongestion;
int bestCity;
int dfs1(int curr, int prev, const int P[]){
int congestion = P[curr];
for(int next : adj[curr]){
if(next != prev){
congestion += dfs1(next, curr, P);
}
}
cong[curr] = congestion;
return congestion;
}
void dfs2(int curr, int prev, const int P[]){
// test
int mostCong = 0;
for(int next : adj[curr]){
mostCong = max(mostCong, cong[next]);
}
// cout << "most for " << curr << " is " << mostCong << "\n";
if(mostCong < minCongestion){
minCongestion = mostCong;
bestCity = curr;
}
for(int next : adj[curr]){
if(next != prev){
// reroot
cong[curr] -= cong[next];
cong[next] += cong[curr];
// go
dfs2(next, curr, P);
// roll back
cong[next] -= cong[curr];
cong[curr] += cong[next];
}
}
}
int LocateCentre(int N, int P[], int S[], int D[]){
for(int i = 0; i < N-1; i++){
int u = S[i];
int v = D[i];
adj[u].push_back(v);
adj[v].push_back(u);
}
// start at 0
bestCity = 0;
minCongestion = 2e9+1e8;
// initialize cong with dfs1
dfs1(0, -1, P);
// // test
// for(int i = 0; i < N; i++){
// cout << i << " : " << cong[i] << "\n";
// }
// reroot with dfs2
dfs2(0, -1, P);
// return
return bestCity;
}
