Educational Codeforces Round 25: G. Tree Queries

http://codeforces.com/contest/825/problem/G

解法

一番最初の黒頂点を根 r として考える。黒頂点に囲まれている部分を black-tree と呼ぶことにする。

タイプ1
u-r パスを black-tree に併合すればいい。事前に r-u パス上の最小頂点を求めておくことで O(1) で併合と同等の操作が行える。

タイプ2
white-path と black-tree の最小値を求めれば良い。white-path を厳密に求める必要はなく、r-u パス上の最小頂点のみを求めれば良い。これも O(1) でできる。

#include <iostream>
#include <algorithm>
#include <vector>

int input() {
    int n;
    scanf("%d", &n);
    return n;
}

int main() {
    int n, q;
    std::cin >> n >> q;

    std::vector<std::vector<int>> g(n);
    for (int i = 0; i < n - 1; i++) {
        int u = input() - 1;
        int v = input() - 1;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    input();
    int root = input() % n;
    q--;

    std::vector<int> white_path(n, -1);
    std::vector<int> stack;
    white_path[root] = root;

    stack.push_back(root);
    while (!stack.empty()) {
        const int u = stack.back();
        stack.pop_back();
        white_path[u] = std::min(u, white_path[u]);

        for (int v : g[u]) {
            if (white_path[v] == -1) {
                white_path[v] = white_path[u];
                stack.push_back(v);
            }
        }
    }

    int ans = 0;
    int black_min = 1e9;
    while (q--) {
        int t = input();
        int x = (input() + ans) % n;

        if (t == 1) {
            black_min = std::min(black_min, white_path[x]);
        } else {
            ans = std::min(white_path[x], black_min) + 1;
            printf("%d\n", ans);
        }
    }
}