Algoogle

Algorithm for Programming Contest

AOJ 2170 Marked Ancestor

Category: AOJ Tag: data-structure

Marked Ancestor

問題概要


木に対する2種類の以下のクエリを処理して出力の総和を求めよ

  • 頂点にマークする
  • 祖先の中で一番近いマークされた頂点を出力しろ

解法


マークするたびにその頂点の子孫の情報を書き換える.
すでにマークされている点や, 同じ情報を持つ点に到達したら打ち切る.

想定解法はクエリを後ろから処理してunion-findで併合していくらしい.

コード


(2170.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i,a) repi(i,0,a)
#define pb push_back
const int inf = 1e9;
int N, Q;
vector<int> ch[100010];
int marked[100010];

void dfs(int v, int a){
    if(marked[v] == v or marked[v] == a) return;
    marked[v] = a;
    rep(i,ch[v].size()) dfs(ch[v][i], a);
}

int solve(){
    memset(marked, 0, sizeof(marked));
    int ans = 0;
    while(Q--){
        char c; int v;
        cin >> c >> v;
        v--;
        if(c == 'Q') ans += marked[v]+1;
        else dfs(v, v);
    }
    return ans;
}

bool input(){
    cin >> N >> Q;
    if(!N and !Q) return 0;
    rep(i,N) ch[i].clear();
    rep(i,N-1) {
        int a; cin >> a;
        ch[a-1].pb(i+1);
    }
    return 1;
}
signed main(){
    while(input()) cout << solve() << endl;
    return 0;
}

Comments