AOJ 2170 Marked Ancestor - mayoko’s diary

問題

ルートが頂点 0 の木が与えられる。頂点 0 の点は最初から黒く, それ以外の点は白い。これについて, 以下の二種類のクエリが投げられるので, 対応する。

頂点 v を選び, その点を黒く塗る。
頂点 v, もしくはその先祖の点で, 黒く塗られていて最も v に近い頂点を求める。

解法

クエリを逆から見ていきます。すると, 「塗られていた点が実は塗られていなかった」というような状況になるので, 黒い頂点が白い頂点になったとき, その点の上下にあった点の集合が合体するようなイメージが湧きます。つまり, union-find 的に解けそうですね。

rank を考慮すると「なにが最も上にある頂点なのか」を管理するのが面倒だったので, dfs の中で par をまとめる高速化しかしていません。が, O(n log n) になることが示されているようです(よくわからない)。

const int MAXN = 100100;
pair<char, int> query[MAXN];

int par[MAXN], cnt[MAXN];

int getPar(int v) {
    if (cnt[v]) return v;
    else return par[v] = getPar(par[v]);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, Q;
    while (cin >> N >> Q) {
        if (N==0 && Q==0) break;
        memset(par, -1, sizeof(par));
        memset(cnt, 0, sizeof(cnt));
        for (int i = 1; i < N; i++) {
            int p;
            cin >> p; p--;
            par[i] = p;
        }
        cnt[0] = 1;
        for (int i = 0; i < Q; i++) {
            cin >> query[i].first >> query[i].second;
            query[i].second--;
            if (query[i].first == 'M') {
                cnt[query[i].second]++;
            }
        }
        ll ans = 0;
        for (int i = Q-1; i >= 0; i--) {
            char c = query[i].first;
            int v = query[i].second;
            if (c == 'M') cnt[v]--;
            else ans += getPar(v)+1;
        }
        cout << ans << endl;
    }
    return 0;
}