#include <bits/stdc++.h>
#define _USE_MATH_DEFINES
#define INF LLONG_MAX
#define MOD 1000000007
#define endl "\n"
#define sp " "
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define f1(i, x) for(auto &i : x)
#define f2(i, x, j) for(ll i = j; i < x; i++)
#define raya() cout << endl << "====================================" << endl
#define dbg(x) cerr << #x << ": " << x << endl;
using namespace std;
using ll = long long;
int sum = 0;
vector<vector<int>> sum1, sum2, arr;
vector<int> P;
vector<bool> vis;
ll dfs(int n){
if(vis[n]) return 0;
vis[n] = 1;
if(arr[n].size() == 1){
sum1[n].push_back(0);
return P[n];
} else {
f1(i, arr[n]){
int aux;
aux = dfs(i);
if(aux){
sum1[n].push_back(aux);
}
}
}
int ans = 0;
f1(i, sum1[n]){
ans += i;
}
sum1[n].push_back(sum - ans - P[n]);
return ans + P[n];
}
int LocateCentre(int n, int p[], int s[], int d[]){
arr.assign(n, vector<int>(0));
sum1.assign(n, vector<int>(0));
sum2.assign(n, vector<int>(0));
f2(i, n, 0){
P.push_back(p[i]);
sum += P[i];
}
vis.assign(n, 0);
int r;
f2(i, n - 1, 0){
arr[s[i]].push_back(d[i]);
arr[d[i]].push_back(s[i]);
}
r = 0;
dfs(r);
int ans = -1;
f1(i, sum1){
int aux = 0;
f1(j, i){
aux = max(j, aux);
}
if(ans == -1){
ans = aux;
}
ans = max(ans, aux);
}
return ans;
}
