#include <iostream>
#include <vector>
#include "traffic.h"
using namespace std;
const int nmax = 1e6 + 5;
vector <int> g[nmax];
int dp[nmax];
int new_dp[nmax];
int v[nmax];
int minim = 2e9 + 5, sol;
int maxim[nmax];
#define pb push_back
void dfs(int nod, int dad = -1)
{
dp[nod] = v[nod];
for (auto x : g[nod])
{
if (dad == x)
continue;
dfs(x, nod);
dp[nod] += dp[x];
maxim[nod] = max(maxim[nod], dp[x]);
}
}
int LocateCentre(int n, int p[], int s[], int d[])
{
int sum = 0, i;
for (i = 0; i < n - 1; i++)
{
g[s[i]].pb(d[i]);
g[d[i]].pb(s[i]);
}
for (i = 0; i < n; i++)
v[i] = p[i], sum += v[i];
dfs(0);
for (i = 0; i < n; i++)
{
maxim[i] = max(maxim[i], sum - dp[i]);
if (minim > maxim[i])
{
minim = maxim[i];
sol = i;
}
}
return sol;
}/*
int p[nmax];
int s[nmax];
int d[nmax];
int main()
{
int n, i;
cin >> n;
for (i = 0; i < n; i++)
cin >> p[i];
for (i = 0; i < n - 1; i++)
cin >> s[i] >> d[i];
cout << LocateCentre(n, p, s, d);
return 0;
}*/
