#include "traffic.h"
#include <bits/stdc++.h>
/**
#pragma GCC optimize ("O3")
#pragma GCC optimize ("fast-math")
#pragma GCC optimize ("unroll-loops")
**/
using namespace std;
//#define int long long
#define ll long long
#define all (x) begin(x), end(x)
#define xx first
#define yy second
using pii = pair <int, int>;
using tii = tuple <int, int, int>;
constexpr int NMAX = (int) 1e6;
vector <int> ans[NMAX + 5];
ll lazy[NMAX + 5];
ll cp[NMAX + 5];
ll s, maxi;
int rez;
inline void dfs (int nod, int parent)
{
ll maxi = 0;
for (auto elem : ans[nod])
{
if (elem == parent)
continue;
dfs (elem, nod);
lazy[nod] += lazy[elem];
maxi = max (maxi, lazy[elem]);
}
cp[nod] = maxi;
}
int LocateCentre(int n,int pp[],int S[],int D[])
{
maxi = INT_MIN;
rez = -1;
for (int i = 0; i < n; ++ i)
{
lazy[i] = pp[i];
s += pp[i];
}
for (int i = 0; i < n - 1; ++ i)
{
ans[S[i]].push_back(S[i]);
ans[D[i]].push_back(D[i]);
}
dfs (0, -1);
for (int i = 0; i < n; ++ i)
{
cp[i] = max (cp[i], s - lazy[i]);
if (cp[i] < maxi)
{
maxi = cp[i];
rez = i;
}
}
return rez;
}
