2170-Marked Ancestor

問題概要

頂点数が100000個以内の木が与えられる．
それに対し100000個以内の2種類の操作が与えられる
M：ある頂点をマークする，既にマークされている場合何もしない．
Q：ある頂点に対し祖先のうち最も近いマークがついた頂点の番号を求める．
Qの操作で求めた番号の総和を求めよ．

解法

前から考えるとUnion-Findの逆の分割の動作が必要になってしまい，解けないが，後ろから考えると単純にUnion-Findしていくだけで解ける．

実装(C++)

#include <algorithm>
#include <vector>
#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
typedef long long int lli;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
int N,Q;
vector<int> children[100000];
int parent[100000];
char marked[100000],s[2];
int stack[100000],stc,a,b,init[100000];
char stack2[100000];
class UnionFind{
private:
	vector<int> par;vector<int> rank;
public:
	UnionFind(int n){
		par=vector<int>(n);rank=vector<int>(n,0);
		for(int i=0;i<n;i++){
			par[i]=i;
		}
	}
	int find(int x){
		if(par[x]==x)
			return x;
		else
			return par[x] = find(par[x]);
	}
	void unite(int x,int y){
		x=find(x);y=find(y);
		if(x==y)return;
		if(rank[x]<rank[y]){
			par[x]=y;
		} else{
			par[y]=x;
			if(rank[x]==rank[y]) rank[x]++;
		}
	}
	inline bool same(int x,int y){
		return find(x)==find(y);
	}
};
void bfs(int k,int value=0){
	queue<int> k_,value_;
	k_.push(k);value_.push(value);
	while(k_.empty()==false){
		value=value_.front();value_.pop();
		k=k_.front();k_.pop();

		if(marked[k]==true)value=k;
		init[k]=value;
		REP(i,children[k].size()){
			k_.push(children[k][i]);
			value_.push(value);
		}
	}
}
int main(){
	for(;;){
		scanf("%d%d",&N,&Q);stc=0;
		if(N==0)break;
		REP(i,N){
			children[i].clear();
			marked[i]=false;
		}
		REP(i,N-1){
			scanf("%d",&b);
			children[--b].push_back(i+1);
			parent[i+1]=b;
		}
		marked[0]=true;
		REP(i,Q){
			scanf("%s%d",s,&a);
			--a;
			if(s[0]=='M'&&marked[a])continue;
			if(s[0]=='M'){
				marked[a]=1;
			}
			stack2[stc]=s[0];
			stack[stc++]=a;
		}
		bfs(0,0);
		UnionFind uf(N);
		init[0]=0;
		REP(i,N){
			uf.unite(i,init[i]);
		}
		long long int ans=0;
		for(int i=--stc;i>=0;i--){
			if(stack2[i]=='Q'){
				ans+=init[uf.find(stack[i])]+1;
			}else{
				int v=init[uf.find(parent[stack[i]])];
				uf.unite(stack[i],parent[stack[i]]);
				init[uf.find(stack[i])]=v;
			}
		}
		cout<<ans<<endl;
	}
}