#include <bits/stdc++.h>
#include "traffic.h"
using namespace std;
const int mxN = 1000005;
vector<int> adj[mxN];
int sum_of_all = 0, sums[mxN], res[mxN];
void dfs(int u, int par, int p[]) {
sums[u] = p[u], res[u] = INT_MIN;
for(auto &v : adj[u]) {
if(v == par) continue;
dfs(v, u, p);
sums[u] += sums[v];
res[u] = max(res[u], sums[v]);
}
res[u] = max(res[u], sum_of_all-sums[u]);
}
int LocateCentre(int n, int p[], int s[], int d[]) {
for(int i = 0; i < n; i++)
sum_of_all += p[i];
for(int i = 0; i < n-1; i++) {
adj[s[i]].push_back(d[i]);
adj[d[i]].push_back(s[i]);
}
dfs(0, -1, p);
int ans = INT_MAX, pos = 0;
for(int i = 0; i < n; i++) {
if(ans > res[i])
ans = res[i], pos = i;
}
return pos;
}
/*
int main() {
int n = 5;
int p[5] = {10, 10, 10, 20, 20};
int s[4] = {0, 1, 2, 3};
int d[4] = {2, 2, 3, 4};
int ans = LocateCentre(n, p, s, d);
for(int i = 0; i < n; i++) {
cout << sums[i] << " " << res[i] << "\n";
}
return 0;
}
*/
