#include "traffic.h" #include <vector> #include <iostream> #define vi vector<int> using namespace std; const int INF = 2000000100; int A[1000001], DP[1000001]; vi adj[1000001]; int best = INF; vi ans; void DFS(int u, int p) { DP[u] = A[u]; for (const int &v : adj[u]) { if (v == p) continue; DFS(v, u); DP[u] += DP[v]; } } void DFS2(int u, int p, int w) { int res = w; for (const int &v : adj[u]) { if (v == p) continue; res = max(res, DP[v]); } if (res < best) {best = res; ans.clear();} if (res == best) ans.push_back(u); w += DP[u]; for (const int &v : adj[u]) { if (v == p) continue; DFS2(v, u, w - DP[v]); } } int LocateCentre(int N, int P[], int S[], int D[]) { for (int i = 0; i < N; i++) A[i] = P[i]; for (int i = 0; i + 1 < N; i++) { adj[S[i]].push_back(D[i]); adj[D[i]].push_back(S[i]); } DFS(0, -1); DFS2(0, -1, 0); return ans[0]; }