#include "traffic.h"
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
vector<vector<int>> g;
vector<ll> subtreeSum;
void dfs(int node, int par, int p[]) {
subtreeSum[node] = p[node];
for (auto &v : g[node]) {
if (v != par) {
dfs(v, node, p);
subtreeSum[node] += subtreeSum[v];
}
}
}
bool check(int x, int n, int p[]) {
ll maxTraffic = 1e9;
for (int i = 0; i < n; i++) {
ll temp = 0;
for (auto &v : g[i]) {
subtreeSum.assign(n, 0);
dfs(v, i, p);
// for (auto &x : subtreeSum) {
// cout << x << " ";
// }
// cout << " -> " << subtreeSum[v] << endl;
temp = max(temp, subtreeSum[v]);
}
maxTraffic = min(maxTraffic, temp);
// cout << endl;
}
return maxTraffic <= x;
}
int LocateCentre(int n, int p[], int s[], int d[]) {
g.resize(n);
for (int i = 0; i < n - 1; i++) {
g[s[i]].push_back(d[i]);
g[d[i]].push_back(s[i]);
}
ll low = 1, high = 2e9, ans = high;
while (low <= high) {
ll mid = low + (high - low) / 2;
if (check(mid, n, p)) {
ans = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
return ans;
}
