mayoko’s diary

プロコンとかいろいろ。

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

解法

ペアプロの動画で一緒に解きました。
続・ペアプログラミング - YouTube

頂点 v から子でも親にもなっていない頂点は, v から dfs して行けない点, および u -> ... -> v と dfs して到達できる点ではない点, の 2 種類です。

これは, dfs をしながら再現できます。具体的には,

  • v に dfs で入った時集合に入ってる値を調べる
  • v の子を調べる
  • dfs で v から出るとき集合に a[v] を加える

子を調べるのは, G[v][i] の i を小さい方からだけでなく, 大きい方からも調べて両側から探索しないといけないことに注意です。

const int MAXN = 100010;
const int INF = 1e9+7;
int N;
int a[MAXN];
pii best[MAXN];
vector<int> G[MAXN], rG[MAXN];
map<int, int> mp;

void dfs(int v, int dir) {
    auto it = mp.upper_bound(a[v]);
    if (it != mp.end()) {
        int tmp = it->first;
        pii p = pii(abs(tmp-a[v]), tmp);
        best[v] = min(best[v], p);
    }
    if (it != mp.begin()) {
        it--;
        int tmp = it->first;
        pii p = pii(abs(tmp-a[v]), tmp);
        best[v] = min(best[v], p);
    }
    int size = G[v].size();
    if (dir == 1) {
        for (int i = 0; i < size; i++) dfs(G[v][i], dir);
    }
    if (dir == -1) {
        for (int i = size-1; i >= 0; i--) dfs(G[v][i], dir);
    }
    mp[a[v]]++;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    for (int i = 0; i < N; i++) cin >> a[i];
    for (int i = 0; i < N-1; i++) {
        int s, t;
        cin >> s >> t;
        G[s].push_back(t);
        rG[t].push_back(s);
    }
    int root = -1;
    for (int i = 0; i < N; i++) if (rG[i].size() == 0) root = i;
    for (int i = 0; i < N; i++) best[i].first = INF;
    dfs(root, 1);
    mp.clear();
    dfs(root, -1);
    for (int i = 0; i < N; i++) {
        if (best[i].first < INF) cout << best[i].second << endl;
        else cout << -1 << endl;
    }
    return 0;
}