Language: C++

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
#define INF (1<<29)


template<class T>
class BinomialHeap{
	struct Tree{
		T val;
		std::vector<Tree *> edge;
		Tree(T &v):val(v){}
		~Tree(){
			for(int i=0;i<degree();i++)delete edge[i];
		}	
		void add(Tree *t){edge.push_back(t);}
		void pop(Tree *t){edge.pop_back();}
		int degree()const{return edge.size();}
	};
	std::vector<Tree*> trees;
	mutable int imax;

	static Tree* add(Tree* a,Tree* b){
		if(a->val > b->val){
			a->add(b);
			return a;
		}else{
			b->add(a);
			return b;
		}
	}
	void findmax()const{
		for(int i=0;i<trees.size();i++)
			if(trees[i] && (imax==-1||trees[i]->val > trees[imax]->val))
				imax=i;
	}
public:
	BinomialHeap():imax(-1){}
	~BinomialHeap(){
		clear();
	}
	//O(log n)
	void meld(BinomialHeap &h){
		imax=-1;
		Tree* carry=NULL;
		if(trees.size()<h.trees.size())trees.swap(h.trees);
		for(int i=0;i<trees.size();i++){
			if(carry==NULL && h.trees.size()<=i)break;
			if(carry){
				if(i<h.trees.size() && h.trees[i]){
					carry=add(carry,h.trees[i]);
				}else if(trees[i]){
					carry=add(carry,trees[i]);
					trees[i]=NULL;
				}else{
					trees[i]=carry;
					carry=NULL;
				}
			}else if(h.trees[i]){
				if(trees[i]){
					carry=add(trees[i],h.trees[i]);
					trees[i]=NULL;	
				}else{
					trees[i]=h.trees[i];	
				}
			}
		}
		if(carry)trees.push_back(carry);
		h.trees.clear();
	}
	//O(log n)
	void insert(T v){
		BinomialHeap h;
		h.trees.push_back(new Tree(v));
		meld(h);
	}
	T getmax()const{
		if(imax==-1)findmax();
		return trees[imax]->val;
	}
	void popmax(){
		if(imax==-1)findmax();
		BinomialHeap h;
		trees[imax]->edge.swap(h.trees);	
		delete trees[imax];
		trees[imax]=NULL;	
		meld(h);
		while(!trees.empty() && trees.back()==NULL)trees.pop_back();
		imax=-1;
	}
	bool empty()const{
		return trees.empty();
	}
	void clear(){
		imax=-1;
		for(int i=0;i<trees.size();i++)
			if(trees[i])
				delete trees[i];
		trees.clear();
	}
	//void remove(int id){}
	//decrease_key remove(int id,T v){}
};



int n,q;
int par[100000];
int marked[100000];
BinomialHeap<int> bh[100000];
vector<int> edge[100000];
long long ans;


vector<int> nodes;

void bfs(){
	nodes.clear();
	int u=0;
	queue<int> q;
	q.push(u);
	while(!q.empty()){
		u=q.front();
		q.pop();
		nodes.push_back(u);
		for(int i=0;i<edge[u].size();i++){
			q.push(edge[u][i]);
		}
	}
}
/*なぜかstack over flowする
void dfs(int u){
	for(int i=0;i<edge[u].size();i++){
		dfs(edge[u][i]);
		bh[u].meld(bh[edge[u][i]]);
	}
	int t=marked[u];
	while(!bh[u].empty() && t<bh[u].getmax()){
		ans+=u+1;
		bh[u].popmax();
	}
}*/


int main(){
	while(cin>>n>>q&&n){
		memset(par,-1,sizeof(par));
		for(int i=0;i<n;i++)edge[i].clear();
		for(int i=0;i<n;i++)bh[i].clear();
		for(int i=0;i<n;i++)marked[i]=INF;
		marked[0]=0;
		for(int i=1;i<n;i++){
			int p;
			cin>>p;
			edge[p-1].push_back(i);
			par[i]=p-1;
		}
		for(int i=0;i<q;i++){
			char op;
			int v;
			cin>>op>>v;
			v--;
			if(op=='M'){
				marked[v]=min(marked[v],i+1);
			}else{
				bh[v].insert(i+1);
			}
		}

		ans=0;
		bfs();
		for(int i=n-1;i>=0;i--){
			int u=nodes[i];
			int t=marked[u];
			while(!bh[u].empty() && t<bh[u].getmax()){
				ans+=u+1;
				cout<<u<<endl;
				bh[u].popmax();
			}
			if(u!=0){
				bh[par[u]].meld(bh[u]);
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

Compiler output:
a.cc: In function 'int main()':
a.cc:149:17: error: 'memset' was not declared in this scope
  149 |                 memset(par,-1,sizeof(par));
      |                 ^~~~~~
a.cc:5:1: note: 'memset' is defined in header '<cstring>'; this is probably fixable by adding '#include <cstring>'
    4 | #include<queue>
  +++ |+#include <cstring>
    5 | using namespace std;