Marked Ancestor (AOJ 2170, JAG Summer 2009)

ライブラリがあれば楽にとけるやつ。HL分解して、マークしたかどうかはBinary Indexed Treeなどを使うだけ。

vector<vi> G(N);
FOR(i, 1, N) {
    int p;
    cin >> p;
    --p;
    G[p].push_back(i);
}

HLDecomposition hld(G);
// 0ならばマークされていない。
// そうでなければマークされている。
BIT bit(N);
bit.add(hld.id[0], 1);
// 解
ll re = 0;
rep(i, Q) {
    char c;
    int v;
    cin >> c >> v;
    --v;
    if (c == 'M') {
        // マークする
        bit.add(hld.id[v], 1);
    } else {
        // 根までの経路を半開区間の集合として得る
        auto H = hld.goUpToLCA(0, v);
        int p = 0;
        // 半開区間は頂点の深さの降順に並んでいる。
        // どの半開区間(経路の一部)に含まれるかを調べる
        // そのうち、深いもの
        for (; !bit.sum(H[p].first, H[p].second); p++);
        // この半開区間(経路の一部にふくまれている。)
        // 半開区間内では頂点は深さの昇順に並んでいる。
        // マークされている頂点を二分探索で求める。
        int ok = H[p].first, ng = H[p].second;
        while (ng - ok > 1) {
            int mid = (ok + ng) / 2;
            // 計算量はO(Nlog(N^2))
            (bit.sum(mid, H[p].second) ? ok : ng) = mid;
        }
        re += hld.ver[ok] + 1;
    }
}
cout << re << endl;