#include "traffic.h"
#include <vector>
#include <iostream>
using namespace std;
using ll = long long;
int const N_MAX = 1e6+10;
ll const INF = 1e18+10;
ll dp[N_MAX];
ll val[N_MAX];
ll sum = 0;
ll fin = INF;
int finnode = 0;
vector<int> adj[N_MAX];
void dfs(int n,int p){
ll ans = 0;
// if(n == 0) cout << "HEHEHEHA " << p << endl;
// cout << "- " << n << " " << p << endl;
for(auto k:adj[n]){
// if(n == 0){
// cout << k << endl;
// }
if(k == p) continue;
dfs(k,n);
dp[n] += dp[k]+val[k];
ans = max(dp[k]+val[k],ans);
}
ll parval = sum-dp[n]-val[n];
ans = max(ans,parval);
//cout << n << " " << ans << endl;
//if(n == 0) cout << ans << endl;
if(fin >= ans){
//cout << n << " " << ans << endl;
fin = ans;
finnode = n;
}
}
int LocateCentre(int n, int pp[], int S[], int D[]) {
for(int i{};i < n;i++){
val[i] = pp[i];
sum += pp[i];
if(i != n-1){
adj[S[i]].emplace_back(D[i]);
adj[D[i]].emplace_back(S[i]);
}
}
dfs(0,-1);
return finnode;
}
