$\text{Link}$

假设只有操作 W，我们可以直接把结点数 $n \to n+1$，然后把 $n$ 和 $x$ 连边，$x$ 为 $n$ 的父结点。

对于操作 Z，相当于要把新结点 $n$ 共享 $x$ 已经进行了的操作。为了避免后续对 $x$ 和 $n$ 各自的操作影响前面这一段共享的操作，我们在原来 $x$ 的位置开一个虚点，继承 $x$ 的所有边，把 $x$ 和 $n$ 的父节点都设为虚点。

现在考虑如何计算贡献，令初始状态下 $1$ 和 $2$ 为关键点，操作 W 增加的点也为关键点。在操作 Z 时，如果 $x$ 原来是关键点，就将虚点置为关键点，$x$ 置为非关键点。定义 $top_x$ 为 $x$ 祖先中最深的关键点。

考虑分别计算将所有点缩到 $top_x$ 后子节点和父节点的贡献。

对于子节点对父节点的贡献，相当于给 $fa_{top_x}$ 的位置加一，查询到 $top$ 的链的贡献。

对于父节点对子节点的贡献，相当于查询 $fa_{top_x}$ 的 $top$ 相同的子树和。

离线下来树状数组即可，复杂度 $O(n \log n)$。

::::info[Code]

#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
const int N=2e6+10;
int n=2,tot,q,fa[N],x[N],root,id[N],pos[N],top[N],dfn[N],siz[N],buf[N],*now;
#define cnt pos
#define ans id
char opt[N];
vector<int>e[N];
bitset<N>b;
struct Fenwick_tree{
	int *t,len;
	inline int lowbit(int x){return x&(-x);}
	inline void add(int x,int val){
	  while(x<=len){
		t[x-1]+=val;
		x+=lowbit(x);
	  }
	}
	inline int sum(int x){
	  int res=0;
	  while(x>0){
		res+=t[x-1];
		x-=lowbit(x);
	  }
	  return res;
	}
	inline void clear(){for(int i=0;i<len;++i)t[i]=0;}
}t[N];
inline void dfs(int u){
	if(b[id[u]])top[u]=u,cnt[u]=0;
	else top[u]=top[fa[u]];
	dfn[u]=++cnt[top[u]];
	siz[u]=1;
	for(int v:e[u]){
	  fa[v]=u;
	  dfs(v);
	  if(top[u]==top[v])siz[u]+=siz[v];
	}
	if(b[id[u]]){
	  t[u].t=now;
	  t[u].len=siz[u];
	  now+=siz[u];
	}
}
signed main(){
	now=buf;
	cin>>q;
	for(int i=1;i<=(q<<1);++i)id[i]=i;
	tot=q;
	fa[2]=1;
	b[1]=b[2]=1;
	for(int i=1;i<=q;++i){
	  cin>>opt[i]>>x[i];
	  if(opt[i]=='W')fa[++n]=id[x[i]],b[n]=1;
	  else if(opt[i]=='Z'){
		fa[++tot]=fa[++n]=id[x[i]];
		swap(id[tot],id[x[i]]);
	  }
	}
	for(int i=1;i<=tot;++i)pos[id[i]]=i;
	for(int i=1;i<=n;++i){
	  if(fa[id[i]])e[pos[fa[id[i]]]].pb(i); 
	  else root=i;
	}
	for(int i=q+1;i<=tot;++i){
	  if(fa[id[i]])e[pos[fa[id[i]]]].pb(i);
	  else root=i;
	}
	fa[root]=0;
	dfs(root);
	n=0;
	++n;
	t[top[n]].add(dfn[n],1);
	++n;
	t[top[n]].add(dfn[n],1);
	for(int i=1;i<=q;++i){
	  if(opt[i]!='?'){
		++n;
		t[top[n]].add(dfn[n],1);
	  }
	  else{
		int u=fa[top[x[i]]];
		if(u)ans[i]=t[top[u]].sum(dfn[u]+siz[u]-1)-t[top[u]].sum(dfn[u]-1);
		else ans[i]=0;
	  }
	}
	for(int i=1;i<=tot;++i)t[i].clear();
	n=0;
	++n;
	int u=fa[top[n]];
	if(u){
	  t[top[u]].add(dfn[u],1);
	  t[top[u]].add(dfn[u]+siz[u],-1);
	}
	++n;
	u=fa[top[n]];
	if(u){
	  t[top[u]].add(dfn[u],1);
	  t[top[u]].add(dfn[u]+siz[u],-1);
	}
	for(int i=1;i<=q;++i){
	  if(opt[i]!='?'){
		++n;
		int u=fa[top[n]];
		if(!u)continue;
		t[top[u]].add(dfn[u],1);
		t[top[u]].add(dfn[u]+siz[u],-1);
	  }
	  else cout<<ans[i]+t[top[x[i]]].sum(dfn[x[i]])<<"\n";
	}
	return 0;
}

::::