Marked Ancestor

問題

Marked Ancestor | Aizu Online Judge

感想

最初は、Disjoint Set（Union-Find木）を使う意味がわからなかった。 単純にクエリごとに親をたどっていきばいいのでは、と思っていました。（愚直解） しかし、愚直解では、根を調べた後にパスを短縮化することができないんですね。これが原因でTLEになります.....いやならないらしいw。

まあ愚直解だと勉強にならないので、ここではUnion-Find木を使って解いてみました。 計算量について、まだまだ考察が甘いなと反省した問題でした。楽しい。

考え

• クエリの後ろから実行する。Mはここでは、Union-Find木でいうuniteに相当する。
• 同じindexへのMは無視する（Aと変換した）
• クエリの最初から実行する時は、クエリとそのindexを保存するとともに、Mであった場合にその親が自分自身であると設定することも忘れない（PPに対応する）

Accepted Program

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

using namespace std;
#define ll long long 

int m[100001];
int P[100001];
int PP[100001];

// initialize
void init (ll n) {
  // P[i] means the parent of 'i'.
  for (ll i = 0; i <= n; i++) {
    P[i] = i;  
    PP[i] = i;  
    m[i] = 0;
  }    
  m[1] = 1;
}
// check the root of 'x'
int root (ll x) {
  if (P[x] == x) {
    return x;  
  }  
  else {
    // cut the path length
    return (P[x] = root (P[x]));  
  }
}
// unite both root of 'x' and 'y'
void unite (ll x, ll y) {
  P[root(x)] = root(y);    
}

int main () {
  ll n, q;
  while (cin >> n >> q && n != 0 && q != 0) {
    init(n);
    long long ans = 0;
    ll sub;
    char subsub;
    for (ll i = 2; i <= n; i++) {
      cin >> sub;
      P[i] = sub;  
      PP[i] = sub;  
    }
    vector<char> ss;
    vector<ll> s;
    for (ll i = 0; i < q; i++) {
      cin >> subsub >> sub;
      ss.push_back(subsub);
      s.push_back(sub);
      if (subsub == 'M') {
        if (m[sub] == 1) {
          ss[i] = 'A';
        }
        else {
          m[sub] = 1; 
          P[sub] = sub;  
        }
      }    
    }
    for (ll i = 0; i < q; i++) {
      subsub = ss[q - 1 - i];
      sub    = s[q - 1 - i];
      if (subsub == 'M') {
        m[sub] = 0;
        P[sub] = PP[sub];
        unite(sub, P[sub]);    
      }    
      if (subsub == 'Q') {
        ans = ans + root(sub);
      }
    }
    cout << ans << endl;
  }
}