#include <bits/stdc++.h>
using namespace std;
void fastIO() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
const int NMAX = 1e6;
int a[NMAX], dp[NMAX], sum[NMAX], ans;
vector<int> G[NMAX];
void dfs1(int u, int parent) {
sum[u] = a[u];
for (int v : G[u])
if (v != parent) {
dfs1(v, u);
sum[u] += sum[v];
if (sum[v] > dp[u])
dp[u] = sum[v];
}
}
void dfs2(int u, int parent, int s) {
if (dp[u] < dp[ans])
ans = u;
for (int v : G[u])
if (v != parent) {
int aux = dp[v];
if (s + a[u] > dp[v])
dp[v] = s + a[u];
dfs2(v, u, s + a[u]);
dp[v] = aux;
}
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
for (int i = 0; i < N - 1; ++i) {
G[S[i]].emplace_back(D[i]);
G[D[i]].emplace_back(S[i]);
}
for (int i = 0; i < N; ++i)
a[i] = pp[i];
dfs1(0, -1);
dfs2(0, -1, 0);
return ans;
}
int N, P[NMAX], S[NMAX], D[NMAX];
int main() {
fastIO();
cin >> N;
for (int i = 0; i < N; ++i)
cin >> P[i];
for (int i = 0; i < N - 1; ++i)
cin >> S[i] >> D[i];
cout << LocateCentre(N, P, S, D) << '\n';
return 0;
}
Compilation message
/tmp/cc4sHlVs.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cc3Lq01H.o:traffic.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
