题目传送门

前置知识：

可持久化线段树合并或点分治。

题意：

• 给出 $n$ 个集合，初始时第 $i$ 个集合 $S_i=\{i\}$。

• 给出 $n-1+k$ 次操作，每次操作为下列三种之一：

  1. 给出 $a,b$，使 $S_a,S_b\gets S_a\cup S_b$。
  2. 给出 $a,d$，问是否有 $d\in S_a$。
  3. 给出 $a$，问有多少集合满足 $a\in S_i$。

• 保证操作 1 恰好出现 $n-1$ 次，且所有操作 1 的 $(a,b)$ 构成一棵树。

• $n,k\le1.2\times10^5$。

方法 1（线段树合并）：

观察操作 1 与 2，容易想到一个熟悉的问题：$n$ 个孤立的点，每次选两个点连边，维护连通块的点集。可以使用并查集 + 线段树合并维护。

本题中不能使用并查集，因为操作 1 并未将 $S_a$、$S_b$ 合并为同一个集合，两者仍然相互独立。但线段树合并仍然可以使用，并且注意到 $S_a$ 大小一定不大于 $a$ 所在的连通块大小，因此时间复杂度一定不大于上题（即 $\mathcal O(n\log^2 n)$）。由于将合并后的线段树复制成两份会导致复杂度错误，所以使用一棵线段树来维护 $S_a$、$S_b$ 两个集合，通过可持久化来保证修改 $S_a$ 时 $S_b$ 不会改变。

既然用线段树维护了点集，询问点是否在集合中显然可以 $\mathcal O(\log n)$ 查询。考虑操作 3。

求有多少集合 $S_i$ 满足 $a\in S_i$ 较为困难，但求有多少 $i$ 满足 $i\in S_a$ 较为容易：答案即为 $S_a$ 的大小，可以在线段树合并的同时维护。而两者可以互相转化：

考虑样例一（边权 $w(a,b)$ 为边 $(a,b)$ 加入的时间）：

由于 $w(1,3)<w(3,4)<w(4,5)$，所以最后 $1\in S_5$。如果将所有边权取反，即倒序加入所有边，则 $w(1,3)>w(3,4)>w(4,5)$，最后 $5\in S'_1$。可以发现当且仅当正序加入所有边后 $a\in S_b$ 时，将所有边权取反后重新倒序加入，最后有 $b\in S'_a$。

所以只需倒序加一次边就能将所有满足 $a\in S_i$ 的 $i$ 都存储到 $S'_a$ 中。但注意到这么做只有在倒序加完所有边后才能得到所有的 $i$，不能处理加完所有边之前的询问。所以在线段树中不再维护每个 $i$ 是否加入，而是对每个时刻 $t$，维护时刻 $t$ 有多少 $i$ 加入。加完边之后，时刻 $t$ 的询问 $\text C\ a$ 统计 $a$ 所对应线段树中的 $[1,t]$ 之和即可。

注意我们在倒序加边，所以在处理时刻 $i$ 加入的边 $(a,b)$ 时，新加入 $S'_a$ 的点 $x$ 不一定是在时刻 $i$ 加入集合的，而可能在这之后。事实上，考虑正序加入的过程，$a$ 被加入 $S_x$ 是在 $b$ 被加入到 $S_x$ 时发生的，而不是在 $a$ 被加入到 $S_b$，即时刻 $i$ 时发生。

对于新加入 $S'_a$ 的点 $x$，$a$ 加入 $S_x$ 的时刻与 $b$ 加入 $S_x$ 的时刻相同，而新加入 $b$ 的点也同理。所以加入 $(a,b)$ 后 $a,b$ 对应的线段树相同（不考虑 $a,b$ 本身的贡献），仍然只需要合并即可。

时间复杂度 $\mathcal O(m\log n+n\log^2n)$，空间复杂度 $\mathcal O(n\log^2n)$，实际空间很难跑满。

代码放在最后。

方法 2（点分治）：

观察询问 1 和 3。在树上对一个点进行全局询问，可以想到点分治。

考虑样例一（边权 $w(a,b)$ 为边 $(a,b)$ 加入的时间）：

假设在时刻 $5$ 后插入一个询问 $\text C\ 3$，则 $S_1,S_3,S_4,S_5$ 都满足 $3\in S_i$。可以发现，$v$ 对询问 $\text C\ u$ 有贡献，当且仅当从 $u$ 到 $v$ 的路径 $\text{path}(u,v)$ 边权递增，且与 $v$ 相连的边（即最大的那条边）的边权不大于询问的时刻。

对于每个分治中心 $x$，我们要处理所有满足 $\text{path}(u,v)$ 经过 $x$ 的二元组 $(u,v)$ 之间的贡献。考虑要对怎样的点处理询问，统计贡献。

由于 $\text{path}(u,v)$ 递增，$\text{path}(u,v)$ 经过 $x$，所以 $\text{path}(u,x),\text{path}(x,v)$ 也递增。故只需要处理所有本层分治中 $\text{path}(x,v)$ 递增的节点 $v$ 对于 $\text{path}(u,x)$ 递增的节点 $u$ 的贡献即可。

注意到满足上述条件并一定不能满足 $\text{path}(u,v)$ 递增，如上图中 $\text{path}(6,1)$ 递增（因为只有一条边），$\text{path}(1,5)$ 递增，但 $\text{path}(6,5)$ 不递增。记 $e(v)$ 为 $v$ 到 $x$ 的路径上与 $x$ 相连的边，还需满足 $w(e(u))<w(e(v))$。可以调整搜索子树的顺序，先搜索 $w(e(u))$ 较大的子树，保证处理询问 $\text C\ u$ 时所有有贡献的节点 $v$ 都满足 $w(e(u))<w(e(v))$。

而要求最靠近 $v$ 的边的边权不大于询问时刻，只需将最靠近 $v$ 的边的边权作为 $v$ 的权值，处理询问时统计权值不大于时刻的 $v$，可以使用树状数组解决。

考虑询问 2。可以发现对于询问 $\text Q\ u\ v$，当且仅当 $\text{path}(v,u)$ 的边权递增，且最靠近 $u$ 的边的边权不大于询问时刻时满足条件。类似于上述转化，也可以在点分治的过程中实现。读者可以自行思考，或参考代码。

分析复杂度。共有 $\log$ 层，每层每个询问会被处理一次，每个点会被处理一次，加上树状数组的 $\log$，复杂度为 $\mathcal O((n+m)\log^2n)$，空间复杂度 $\mathcal O(n)$。

线段树合并代码：

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i=l, _=r; i<=_; ++i)
using namespace std;
typedef long long ll;
bool Mbe;
const int mN=1.2e5+9, mS=3.5e7;
int n, k, qn[mN*2][2];
bool ans[mN*2];

namespace SGT {	//线段树
#define lc(p) tr[p].son[0]
#define rc(p) tr[p].son[1]
	struct Node {int son[2], siz;} tr[mS];
	int on, rt[mN];
	void modify(int lp, int &p, int l, int r, int x) {	//在 x 处增加 1，记得可持久化
		tr[p=++on]=tr[lp], ++tr[p].siz;
		if(l==r) return;
		int mid=l+r>>1;
		x<=mid? modify(lc(lp), lc(p), l, mid, x): modify(rc(lp), rc(p), mid+1, r, x);
	}
	void merge(int &p, int q1, int q2) {	//合并
		if(!q1 || !q2) return p=q1|q2, void();
		tr[p=++on].siz=tr[q1].siz+tr[q2].siz;
		merge(lc(p), lc(q1), lc(q2)), merge(rc(p), rc(q1), rc(q2));
	}
	inline bool query1(int p, int l, int r, int x) {	//询问是否存在 x 点
		while(l^r) {
			int mid=l+r>>1;
			x<=mid? (p=lc(p), r=mid): (p=rc(p), l=mid+1);
			if(!p) return 0;
		}
		return 1;
	}
	inline int query2(int p, int l, int r, int x) {	//询问 [1,x] 有多少点
		int res=0;
		while(r>x) {
			int mid=l+r>>1;
			x<=mid? (r=mid, p=lc(p)): (res+=tr[lc(p)].siz, l=mid+1, p=rc(p));
			if(!p) return res;
		}
		return res+tr[p].siz;
	}
#undef lc
#undef rc
}
using namespace SGT;

bool Men;
int main() {
	cerr<<"memory: "<<(&Men-&Mbe>>20)<<"MB"<<endl, 0;
	scanf("%d%d", &n, &k);
	rep(i, 1, n) modify(0, rt[i], 1, n, i);	//初始化，每个集合都只包含自己

	rep(i, 1, n-1+k) {
		char opt;
		int x, y;
		scanf("\n%c%d", &opt, &x);
		if(opt^'C') scanf("%d", &y);

		if(opt=='S') merge(rt[x], rt[x], rt[y]), rt[y]=rt[x], qn[i][0]=x, qn[i][1]=y;  
		//合并后 x y 的集合相同，因此 rt[y]=rt[x]；可持久化，所以一个被合并时另一个不会改变
		else if(opt=='Q') ans[i]=query1(rt[x], 1, n, y);
		else qn[i][0]=x;
	}
	memset(tr, 0, sizeof tr), on=n;
	rep(i, 1, n) rt[i]=i;	//倒着做之前重新初始化，每个集合都为空

	for(int i=n-1+k; i>=1; --i) if(qn[i][1]) {	//即，if( 第 i 次操作为操作 1)
		int x=qn[i][0], y=qn[i][1];
		merge(rt[x], rt[x], rt[y]), modify(rt[x], rt[x], 1, n-1+k, i), rt[y]=rt[x];
		//点 x 在时刻 t 加入 Sy，点 y 在时刻 t 加入 Sx，两者都是在时刻 t 增加了一个节点，所以 x,y 对应的线段树是一样的
	}
	rep(i, 1, n-1+k)
		if(!qn[i][0]) puts(ans[i]? "yes": "no");	//操作 2
		else if(!qn[i][1]) printf("%d\n", query2(rt[qn[i][0]], 1, n-1+k, i)+1);	//操作 3
	return 0;
}

点分治代码：

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i=l, _=r; i<=_; ++i)
#define lfor(t, y, x) for(int t=head[x], y; y=e[t][1], t; t=e[t][0])
using namespace std;
typedef long long ll;
inline void to_max(int &x, int y) {if(x<y) x=y;}
bool Mbe;
const int mN=1.2e5+9;
int n, k, ans[mN], qn[mN];
//ans 表示答案，-1(no) / -2(yes) 表示 Q 操作的答案，其他表示 C 操作的答案
//qn 表示时间的映射，qn[i]=j 表示第 i 个询问是在第 j 条边后，第 j+1 条边前提出的

int oe=1, head[mN], e[mN*2][2];
//oe=1 是为了让编号为 t 的边恰好是第 t/2 条边
inline void adde(const int x, const int y) {e[++oe][0]=head[x], e[head[x]=oe][1]=y;}

vector<int> C[mN];
vector<pair<int, int> > Q[mN];

//timh/timt 是懒惰删除，当 tim_[i]!=T 时表示对应数组所含信息没有意义
int T, hav[mN], timh[mN];
//hav 若有意义，hav[i]=j 表示 path(x, i) 中距离 i 最近的边是第 j 条被加入的边
int tr[mN], timt[mN];	//树状数组
inline void add(int x, const int z) {for(; x<=n; x+=x&-x) timt[x]^T? timt[x]=T, tr[x]=z: tr[x]+=z;}
inline int ask(int x) {
	int res=0;
	for(; x; x^=x&-x) timt[x]^T? timt[x]=T, tr[x]=0: res+=tr[x];
	return res;
}

bool mark[mN];
int siz[mN], rt, tot, krt;
void dfs_rt(int x, int f) {	//找重心
	int k=(siz[x]=1, 0);
	lfor(t, y, x) if(y^f && !mark[y]) dfs_rt(y, x), to_max(k, siz[y]), siz[x]+=siz[y];
	if(to_max(k, tot-siz[x]), k<krt) rt=x, krt=k;
}
void dfs_add(int x, int lst) {	//处理 x 的贡献
	if(timh[x]^T) timh[x]=T;	//使数组有意义
	hav[x]=lst, add(lst, 1);
	lfor(t, y, x) if(t>>1>lst && !mark[y]) dfs_add(y, t>>1);	//t>>1>lst 保证递增
}
void dfs_que(int x, int lst) {	//处理 x 的询问
	for(auto it: Q[x]) {
		int t=it.first, y=it.second;
		if(timh[y]==T && hav[y]<=qn[t]) ans[t]=-2;	//如果 y 数组有意义且距离 y 最近的边边权不大于询问时刻
	}
	for(int t: C[x]) ans[t]+=ask(qn[t]);	//统计 [1, qn[t]] 的边的贡献
	lfor(t, y, x) if(t>>1<lst && !mark[y]) dfs_que(y, t>>1);	//t>>1<lst 保证递减
}
void dfs(int x) {
	krt=tot=siz[x], dfs_rt(x, 0), mark[x=rt]=1;
	timh[x]=++T;	//++T 为清空
	lfor(t, y, x) if(!mark[y]) add(hav[x]=t>>1, 1), dfs_que(y, t>>1), dfs_add(y, t>>1), add(t>>1, -1);
	//按照加边顺序的倒序访问每个子树，保证 w(e(u))<w(e(v))
	//hav[x]=t>>1, add(t>>1, 1) 为处理 x 对询问的贡献，add(t>>1, -1) 为撤销
	hav[x]=0;	//特判 Q x y 中 x=y 的情况
	for(auto it: Q[x]) {
		int t=it.first, y=it.second;
		if(timh[y]==T && hav[y]<=qn[t]) ans[t]=-2;
	}
	for(int t: C[x]) ans[t]+=ask(qn[t]);
	lfor(t, y, x) if(!mark[y]) dfs(y);
}

bool Men;
int main() {
	cerr<<"memory: "<<(&Men-&Mbe>>20)<<"MB"<<endl, 0;

	scanf("%d%d", &n, &k);
	rep(i, 1, n-1+k) {
		char opt;
		int x, y;
		scanf("\n%c%d", &opt, &x);
		if(opt^'C') scanf("%d", &y);

		if(opt=='S') adde(x, y), adde(y, x);
		else if(opt=='Q') Q[y].push_back(make_pair(i-oe/2, x)), qn[i-oe/2]=oe/2, ans[i-oe/2]=-1;
		//初始赋为没有找到
		else C[x].push_back(i-oe/2), qn[i-oe/2]=oe/2;
	}
	siz[1]=n, dfs(1);
	rep(i, 1, k) ans[i]<0? puts(~ans[i]? "yes": "no"): printf("%d\n", ans[i]+1);
	return 0;
}