#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
const int MX = 1e6;
int totalFans = 0;
vector<int> roads[MX], cityFans(MX), congestionOfCity(MX), accFans2City(MX);
void dfs (int node, int parent) {
for (auto x: roads[node]) {
if (x == parent) continue;
dfs(x, node);
accFans2City[node] += accFans2City[x];
congestionOfCity[node] = max(congestionOfCity[node], accFans2City[x]);
}
congestionOfCity[node] = max(congestionOfCity[node], totalFans - accFans2City[node] - cityFans[node]);
accFans2City[node] += cityFans[node];
}
int LocateCentre (int n, int p[], int d[], int s[]) {
for (int i = 0; i < n; i++) {
totalFans += p[i];
cityFans[i] = p[i];
}
for (int i = 0; i < n - 1; i++) {
roads[s[i]].push_back(d[i]);
roads[d[i]].push_back(s[i]);
}
dfs(0, -1);
int minIdx = 0;
for (int i = 1; i < n; ++i) {
if (congestionOfCity[i]<congestionOfCity[minIdx]) {
minIdx = i;
}
}
return minIdx;
}
