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;