AOJ 2170 Marked Ancestor
問題
Marked Ancestor | Aizu Online Judge
ルートが頂点 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; }