2170.cpp

aoj2170.cpp

#include <cstdio>
#include <queue>
#define MAX 100001

using namespace std;

int mark[MAX],t[MAX];

int query(int v){
  if(mark[v]) return v;
  else{
    int a = query(t[v]);
    t[v] = a;
    return a;
  }
}

int main(){
  int n,q;
  while(scanf("%d %d",&n,&q),n){
    int ans=0;
    deque<pair<char,int> > qs;

    for(int i=1; i<=n; i++) mark[i]=0; mark[1]=1;

    for(int i=2; i<=n; i++){
      int p;
      scanf("%d",&p);
      t[i] = p;
    }

    for(int i=0; i<q; i++){
      char order; int v;
      scanf(" %c %d",&order,&v);
      if(order=='M') mark[v]++;
      qs.push_front(make_pair(order,v));
    }

    for(int i=0; i<qs.size(); i++)
      if(qs[i].first=='Q')
	ans += query(qs[i].second);
      else
	mark[qs[i].second]--;

    printf("%d\n",ans);
  }
}