#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define ll long long template <class T> bool ckmax(T &a, T b) { return a < b ? (a = b, true) : false; } template <class T> bool ckmin(T &a, T b) { return a > b ? (a = b, true) : false; } const int MAXN = 1e6 + 5; vector<int> g[MAXN]; int p[MAXN], dpPar[MAXN], node = 1; ll sum[MAXN], tot = 0, ans = 1e18; void dfs(int u, int pa) { ll res = 0; sum[u] = p[u]; for (int v : g[u]) { if (v != pa) { dfs(v, u); sum[u] += sum[v]; ckmax(res, sum[v]); } } ckmax(res, tot - sum[u]); if (ckmin(ans, res)) node = u; } int LocateCentre(int N, int pp[], int S[], int D[]) { memcpy(p, pp, N * sizeof(int)); for (int i = 0; i < N - 1; i++) { g[S[i]].emplace_back(D[i]); g[D[i]].emplace_back(S[i]); } tot = accumulate(p, p + N, 0LL); dfs(0, 0); return node; }