#include "traffic.h"
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
vector<vector<int>> gra;
vector<int> we, rou;
priority_queue<pair<pair<int,int>,int>, vector<pair<pair<int,int>,int>>, greater<pair<pair<int,int>,int>>> Q;
int dfs(int x, int p, int t){
if(t == x){
rou.push_back(x);
return 1;
}
for(auto y : gra[x]){
if(y == p)continue;
if(dfs(y,x,t)){
rou.push_back(x);
return 1;
}
}
return 0;
}
int dfs2(int x, int p1, int p2){
int sum = we[x];
for(auto y : gra[x]){
if(y == p1 || y == p2)continue;
sum+=dfs2(y,x,x);
}
return sum;
}
void bfs(pair<pair<int,int>,int> node){
for(auto x : gra[node.f.s]){
if(node.s == x)continue;
Q.push({{node.f.f+we[x],x},node.f.s});
}
}
int LocateCentre(int n, int pp[], int s[], int d[]) {
if(n == 1)return 0;
gra.resize(n);
for(int i = 0; i < n; ++i){
we.push_back(pp[i]);
}
for(int i = 0; i < n-1; i++){
gra[s[i]].push_back(d[i]);
gra[d[i]].push_back(s[i]);
}
Q.push({{we[0],0},0});
pair<pair<int,int>,int> firs,last;
while(!Q.empty()){
auto x = Q.top();
Q.pop();
firs = x;
bfs(x);
}
Q.push({{we[firs.f.s],firs.f.s},firs.f.s});
while(!Q.empty()){
auto x = Q.top();
Q.pop();
last = x;
bfs(x);
}
dfs(firs.f.s, firs.f.s, last.f.s);
int maxi = we[rou[0]]+we[rou[(int)rou.size()-1]];
for(int i = 1; i < (int)rou.size()-1; ++i){
we[rou[i]] = dfs2(rou[i],rou[i-1],rou[i+1]);
maxi+=we[rou[i]];
}
pair<int,int> best = {maxi,-1};
int c1 = 0, c2 = best.f;
for(int i = 0; i < (int)rou.size(); ++i){
if(i)c1+=we[rou[i-1]];
c2-=we[rou[i]];
if(best.f >= max(c1,c2)){
best = make_pair(min(best.f,max(c1,c2)),rou[i]);
}
}
return best.s;
}
