#include <bits/stdc++.h>
#include "traffic.h"
#define ll long long
using namespace std;
vector<ll> dp;
vector<vector<int>> lst;
pair<int,ll> ans;
ll total = 0;
ll dfs(int nodo, int padre, int *p){
ll res = 0;
dp[nodo] = p[nodo];
for(auto vecino:lst[nodo]){
if(vecino==padre) continue;
dp[nodo] += dfs(vecino,nodo,p);
res = max(res, dp[vecino]);
}
res = max(res,total-dp[nodo]);
//cout << "arena: " << nodo << " res: " << res << endl;
if(res<ans.second){
//cout << "update! new arena: " << nodo << " " << res << endl;
ans.second = res;
ans.first = nodo;
}
return dp[nodo];
}
int LocateCentre(int n, int *p, int *s, int *d){
ans.first = 0;
ans.second = 1e18;
lst = vector<vector<int>>(n,vector<int>());
dp = vector<ll>(n);
for(int i=0;i<n-1;i++){
lst[s[i]].push_back(d[i]);
lst[d[i]].push_back(s[i]);
total += p[i];
}
total += p[n-1];
dfs(0,0,p);
return ans.first;
}
/*
int main(){
cout << LocateCentre(5,{10,10,10,20,20},{0,1,2,3},{2,2,3,4}) << endl;
return 0;
}
*/
// vector<int>, int*
