東京大学プログラミングコンテスト2013 I: 支配と友好

問題

I: 支配と友好 - 東京大学プログラミングコンテスト2013 | AtCoder

解法

2回オイラーツアーするだけ。勝手に根が0だと思い込んで（しかもサンプルがそれで合う）メッチャハマった。

コード

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

typedef long long ll;

const int INF = 1e9 + 7;

vector<vector<int>> g;
set<int> double_appear;
vector<int> a;
vector<pair<int, int>> ans;

void dfs(int cur, int prev, bool left) {
  if (!double_appear.empty()) {
    auto it = double_appear.lower_bound(a[cur]);
    if (it != double_appear.end()) {
      ans[cur] = min(ans[cur], {*it - a[cur], *it});
    }
    if (it != double_appear.begin()) {
      it--;
      ans[cur] = min(ans[cur], {a[cur] - *it, *it});
    }
  }

  if (left) {
    for (int i = 0; i < g[cur].size(); ++i) {
      if (g[cur][i] == prev) continue;
      dfs(g[cur][i], cur, true);
    }
  } else {
    for (int i = g[cur].size() - 1; i >= 0; --i) {
      if (g[cur][i] == prev) continue;
      dfs(g[cur][i], cur, false);
    }
  }
  double_appear.insert(a[cur]);
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll N;
  cin >> N;
  a.resize(N);
  for (int i = 0; i < N; ++i) cin >> a[i];

  g.resize(N);
  vector<bool> is_root(N, true);
  for (int i = 0; i < N - 1; ++i) {
    int s, t;
    cin >> s >> t;
    is_root[t] = false;
    g[s].push_back(t);
    g[t].push_back(s);
  }

  int root = -1;
  for (int i = 0; i < N; ++i)
    if (is_root[i]) {
      root = i;
      break;
    }
  assert(root >= 0);

  ans.assign(N, {INF, -1});
  double_appear.clear();
  dfs(root, -1, true);
  double_appear.clear();
  dfs(root, -1, false);
  for (int i = 0; i < N; ++i) {
    cout << ans[i].second << "\n";
  }
}