#include "traffic.h"
#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 LocateCentre(int n, int p[], int s[], int d[]){
vector<vector<int>> arr(n);
vector<int> sum(n), pref(n + 1);
for(int i = 0; i < n; i++){
arr[s[i]].push_back(d[i]);
arr[d[i]].push_back(s[i]);
}
int strt;
for(int i = 0; i < n; i++){
if(arr[i].size() == 1){
strt = i;
break;
}
}
stack<int> dfs;
dfs.push(strt);
vector<bool> vis(n, 0);
while(!dfs.empty()){
int a = dfs.top();
dfs.pop();
if(vis[a]) continue;
vis[a] = 1;
sum[a] = p[a];
f1(i, arr[a]){
dfs.push(i);
}
}
f2(i, n, 0)
pref[i + 1] = sum[i] + pref[i];
int ansa = 1, auxsum = pref[n];
f2(i, n + 1, 1){
int x = pref[i - 1];
int y = pref[n] - pref[i];
if(x + y < auxsum){
auxsum = x + y;
ansa = i;
}
}
return ansa;
}
