#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repb(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define all(A) A.begin(),A.end()
#define allr(A) A.rbegin(),A.rend()
#define precise(i) fixed << setprecision(i)
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define err() cout<<"\n==================================\n";
#define errA(A) for(auto i:A) cout<<i<<" "; cout<<"\n";
#define err1(a) cout<<#a<<" "<<a<<"\n";
#define err2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<"\n";
#define err3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<"\n";
#define err4(a,b,c,d) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<" "<<#d<<" "<<d<<"\n";
#define Pii pair<int,int>
#define Vi vector<ll>
#define Vpii vector<Pii>
Vi adj[1000003];
Vi loc(1000003);
Vi ans(1000003);
Vi subtree(1000003);
ll tot;
void dfs(int x, int p)
{
subtree[x]+= loc[x];
for(auto e: adj[x])
{
if(e != p)
{
dfs(e, x);
subtree[x]+= subtree[e];
ans[x]= max(ans[x], subtree[e]);
}
}
ans[x]= max(ans[x], tot-subtree[x]);
}
int LocateCentre(int n, int p[], int s[], int d[])
{
tot= 0;
rep(c,0,n)
{
loc[c]= p[c];
tot+= p[c];
}
rep(c,0,n-1)
{
adj[s[c]].pb(d[c]);
adj[d[c]].pb(s[c]);
}
dfs(0, -1);
int res;
ll val= 1e18;
rep(c,0,n)
{
if(ans[c] < val)
{
res= c;
val= ans[c];
}
}
return res;
}
