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