#include<bits/stdc++.h>
#include "traffic.h"
using namespace std;
const int maxN = 1e6+1;
int n;
int fans[maxN];
int t_fans = 0;
vector<int> paths[maxN];
//bool vis[maxN];
int dp[maxN][2]; // 0 = Total number of fans in the subtree // 1 = best option
void dfs(int node, int par){
dp[node][0] = fans[node];
int mx_fans = 0;
for(int i : paths[node]){
if(i != par){
dfs(i, node);
dp[node][0] += dp[i][0];
mx_fans = max(mx_fans, dp[i][0]);
}
}
//cout << node << ' ' << mx_fans << '\n';
dp[node][1] = max(mx_fans, max(dp[node][0] - fans[node], t_fans - dp[node][0]));
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
n = N;
memset(fans, 0, sizeof(fans));
//memset(vis, false, sizeof(fans));
for(int i = 0; i < n; ++i){
fans[i] = pp[i];
t_fans += pp[i];
if(i != n-1){
paths[S[i]].push_back(D[i]);
paths[D[i]].push_back(S[i]);
}
}
dfs(0,0);
//for(int i = 0; i < n; ++i) cout << dp[i][0] << ' ' << dp[i][1] << '\n';
int ans = 0;
for(int i = 0; i < n; ++i){
if(dp[i][1] < dp[ans][1]) ans = i;
}
//cout << dp[ans][1] << '\n';
return dp[ans][1];
}
