#include "traffic.h"
#include <vector>
using namespace std;
using ll = long long;
int LocateCentre(int n, int P[], int S[], int D[])
{
vector<ll> val(n);
for (int i = 0; i < n; ++i) val[i] = P[i];
vector<vector<int>> adj(n);
for (int i = 0; i + 1 < n; ++i)
{
adj[S[i]].push_back(D[i]);
adj[D[i]].push_back(S[i]);
}
vector<ll> dp = val;
auto dfs1 = [&dp, &adj](auto self, int v, int p) -> ll
{
for (int u : adj[v]) if (u != p) dp[v] += self(self, u, v);
return dp[v];
};
dfs1(dfs1, 0, -1);
auto dfs2 = [&dp, &adj, &val](auto self, int v, int p, ll dpP) -> pair<ll, int>
{
pair<ll, int> res{dpP, v};
dpP += val[v];
for (int u : adj[v]) if (u != p)
{
res.first= max(res.first, dp[u]);
dpP += dp[u];
}
for (int u : adj[v]) if (u != p)
{
pair<ll, int> ret = self(self, u, v, dpP - dp[u]);
if (ret.first < res.first) res = ret;
}
return res;
};
return dfs2(dfs2, 0, -1, 0).second;
}
