らての精進日記

修行をします

aoj2170:Marked Ancestor

解法

ある頂点をmarkすると、その頂点を根とする部分木に含まれる頂点たちのみが影響を受ける。部分木に対して高速に操作をしたいので、オイラーツア―の列を求めて、segment_treeに載せる。


よくある筋肉実装問題だしなんで星5個もついてるんだ・・・みたいな気持ちになったけど、他人の解答みたら頭良すぎて泣きそうになった。

#include<bits/stdc++.h>
using namespace std;

struct segment_tree{
    static const int SEG=1<<17;
    vector<int>dat;
    segment_tree():dat(SEG*2){}
    void update(int a,int b,int x,int k=0,int l=0,int r=SEG){
        if(r<=a||b<=l)return;
        if(a<=l&&r<=b){
            dat[k]=max(dat[k],x);
            return;
        }
        update(a,b,x,k*2+1,l,(l+r)/2);
        update(a,b,x,k*2+2,(l+r)/2,r);
    }
    int query(int k){
        k+=SEG-1;
        int ret=dat[k];
        while(k){
            k=(k-1)/2;
            ret=max(ret,dat[k]);
        }
        return ret;
    }
};

const int SIZE=100000;

int N,Q;
vector<int>G[SIZE];

int tt,tin[SIZE],tout[SIZE];
int par[20][SIZE],dep[SIZE];
void dfs(int v,int p,int d){
    par[0][v]=p;
    dep[v]=d;
    tin[v]=tt++;
    for(auto u:G[v])dfs(u,v,d+1);
    tout[v]=tt;
}

int main(){
    while(scanf("%d%d",&N,&Q),N||Q){
        for(int i=0;i<N;i++)G[i].clear();
        for(int i=1;i<N;i++){
            int p;scanf("%d",&p);p--;
            G[p].push_back(i);
        }
        tt=0;
        dfs(0,-1,0);

        for(int i=0;i<19;i++){
            for(int j=0;j<N;j++){
                if(par[i][j]==-1)par[i+1][j]=-1;
                else par[i+1][j]=par[i][par[i][j]];
            }
        }

        segment_tree seg;
        long long ans=0;
        while(Q--){
            char c;
            int v;
            scanf(" %c%d",&c,&v);
            v--;
            if(c=='M'){
                seg.update(tin[v],tout[v],dep[v]);
            }
            else{
                int d=seg.query(tin[v]);
                for(int i=19;i>=0;i--)if((dep[v]-d)>>i&1)v=par[i][v];
                ans+=v+1;
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}