Submission #30858093

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;

  priority_queue<pair<int, int>> q;
  q.emplace(0, 0);
  for (int i = 1; i < N; i++) {
    int A;
    cin >> A;
    q.emplace(A, i);
  }

  vector<vector<int>> g(N);
  for (int i = 1; i < N; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }

  vector<int> parents(N);
  function<void(int, int)> dfs = [&](int x, int p) {
    parents[x] = p;
    for (int nx : g[x]) {
      if (nx != p) {
        dfs(nx, x);
      }
    }
  };
  // N: no parent
  dfs(0, N);

  // -1: non-zero, else: next candidate for non-zero
  vector<int> skip(N + 1, -1);
  // find the nearest non-zero ancestor
  function<int(int)> find_non_zero = [&](int x) {
    // path compression like DSU
    return skip[x] == -1 ? x : skip[x] = find_non_zero(skip[x]);
  };

  while (true) {
    auto [a, x] = q.top();
    q.pop();

    int non_zero = find_non_zero(parents[x]);
    if (non_zero == N) {
      cout << a << endl;
      break;
    }
    // replace with zero and set candidate
    skip[non_zero] = parents[non_zero];
  }
}

Submission Info

Judge Result