#include "traffic.h"
#include <vector>
using namespace std;
vector<int> sub(1000001),parent(1000001);
vector<vector<int>> graph(1000001);
vector<int> 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]);
}
dfs(1,-1);
int mn=2e9;
for (int u=1;u<=N;u++){
int c=0;
for (int v:graph[u]){
int comp=0;
if (parent[u] == v){
comp = sub[1]-sub[u];
}else{
comp = sub[v];
}c=max(comp,c);
}
if (c!=0)mn=min(mn,c);
}return mn;
}
