#include "traffic.h"
#include <vector>
using namespace std;
vector<long long> sub(1000001),parent(1000001);
vector<vector<int>> graph(1000001);
vector<long long> arr(1000001);
int dfs(int u,int p){
sub[u] = arr[u];
parent[u] = p;
for (int v:graph[u]){
if (v == p) continue;
sub[u] += dfs(v,u);
}return sub[u];
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
for (int i=0;i<N;i++){
arr[i]=pp[i];
}
for (int i=0;i<N-1;i++){
graph[S[i]].push_back(D[i]);
graph[D[i]].push_back(S[i]);
}
long long mx=0;
for (int i=0;i<N;i++){
dfs(i,-1);
long long mn=4e18;
for (int u=0;u<N;u++){
long long c=0;
for (int v:graph[u]){
long long comp=0;
if (parent[u] == v){
comp = sub[1]-sub[u];
}else{
comp = sub[v];
}c=max(comp,c);
}
mn=min(mn,c);
}mx=max(mx,mn);
}
return mx;
}
