#include <iostream>
#include <vector>
using namespace std;
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
vl DP;
vvi G;
ll dfs(int S, int par) {
ll ans = DP[S];
for (int i = 0; i < (int) G[S].size(); i++) {
int v = G[S][i];
if (v == par) continue;
ans += dfs(v, S);
}
return DP[S] = ans;
}
int LocateCentre(int N, int P[], int S[], int D[]) {
DP = vl(N);
G = vvi(N, vi());
for (int i = 0; i < N-1; i++) {
G[S[i]].emplace_back(D[i]);
G[D[i]].emplace_back(S[i]);
DP[i] = (ll) P[i];
}
DP[N-1] = (ll) P[N-1];
dfs(0, -1);
int ans = 0;
ll rec = 0, cur;
for (int i = 0; i < (int) G[0].size(); i++) {
rec = max(rec, DP[G[0][i]]);
}
int v;
for (int i = 1; i < N; i++) {
cur = DP[0] - DP[i];
for (int j = 0; j < (int) G[i].size(); j++) {
v = G[i][j];
if (DP[v] < DP[i]) cur = max(cur, DP[v]);
}
if (cur < rec) {
rec = cur;
ans = i;
}
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int N;
cin >> N;
int P[N], S[N-1], D[N-1];
for (int i = 0; i < N; i++) cin >> P[i];
for (int i = 0; i < N-1; i++) {
cin >> S[i];
cin >> D[i];
}
cout << LocateCentre(N, P, S, D);
return 0;
}
Compilation message
/tmp/cc4lLWR6.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cclK0bDg.o:traffic.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
