Description：

给一棵树和一个集合，支持删一条边加一条边，向集合中添加点对，删除点对，询问集合中点对之间的路径是否都经过某条边。

$1\leqslant n\leqslant 10^5$

Solution：

一个非常巧妙的转化，就是利用异或哈希，为每个点对随机一个权值，然后问题就变成了询问一个子树的异或和是否等于所有点对的异或和，可以用 $LCT$ 维护子树异或和，每次 $makeroot(x)$ ，那 $y$ 存的虚儿子的值就是子树和。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m;

#define MAXN 100010

typedef long long ll;

ll xorsum = 0;

struct node

{

	int c[2],fa;

	ll tot,sum;

	bool rev;

	node(){tot = sum = 0;}

}t[MAXN];

bool isroot(int k){return (t[t[k].fa].c[0] != k && t[t[k].fa].c[1] != k);}

int id(int k){return (t[t[k].fa].c[0] == k ? 0 : 1);}

void connect(int k,int f,int p){t[k].fa = f;t[f].c[p] = k;return;}

void maintain(int k){t[k].sum = t[k].tot ^ t[t[k].c[0]].sum ^ t[t[k].c[1]].sum;return;}

void pushdown(int k)

{

	if(t[k].rev)

	{

		t[t[k].c[0]].rev ^= 1;t[t[k].c[1]].rev ^= 1;

		swap(t[k].c[0],t[k].c[1]);t[k].rev ^= 1;

	}

	return;

}

void rotate(int x)

{

	int y = t[x].fa,z = t[y].fa,fx = id(x),fy = id(y);

	if(!isroot(y))t[z].c[fy] = x;

	t[x].fa = z;

	connect(t[x].c[fx ^ 1],y,fx);

	connect(y,x,fx ^ 1);

	maintain(y);maintain(x);

	return;

}

stack<int> s;

void splay(int x)

{

	s.push(x);

	for(int i = x;!isroot(i);i = t[i].fa)s.push(t[i].fa);

	while(!s.empty()){pushdown(s.top());s.pop();}

	while(!isroot(x))

	{

		int y = t[x].fa;

		if(isroot(y)){rotate(x);break;}

		if(id(x) == id(y)){rotate(y);rotate(x);}

		else{rotate(x);rotate(x);}

	}

	return;

}

void access(int k)

{

	for(int i = 0;k;i = k,k = t[k].fa)

	{

		splay(k);

		t[k].tot ^= t[t[k].c[1]].sum;

		t[k].tot ^= t[i].sum;

		t[k].c[1] = i;

		maintain(k);

	}

	return;

}

void makeroot(int k){access(k);splay(k);t[k].rev ^= 1;return;}

void link(int x,int y){makeroot(x);makeroot(y);t[y].tot ^= t[x].sum;t[x].fa = y;maintain(y);return;}

void cut(int x,int y){makeroot(x);access(y);splay(y);t[x].fa = t[y].c[0] = 0;maintain(y);return;}

struct point

{

	int x,y;

	ll v;

}p[300010];

int cur = 0;

int main()

{

	rd();

	n = rd();m = rd();

	for(int i = 1;i < n;++i)link(rd(),rd());

	int opt,x,y;

	for(int i = 1;i <= m;++i)

	{

		opt = rd();

		if(opt == 1)

		{

			x = rd();y = rd();cut(x,y);

			x = rd();y = rd();link(x,y);

		}

		if(opt == 2)

		{

			++cur;

			p[cur].x = x = rd();p[cur].y = y = rd();

			p[cur].v = 1ll * rand() * rand() * rand();

			xorsum ^= p[cur].v;

			makeroot(x);t[x].tot ^= p[cur].v;maintain(x);

			makeroot(y);t[y].tot ^= p[cur].v;maintain(y);

		}

		if(opt == 3)

		{

			x = rd();

			xorsum ^= p[x].v;

			makeroot(p[x].x);t[p[x].x].tot ^= p[x].v;maintain(p[x].x);

			makeroot(p[x].y);t[p[x].y].tot ^= p[x].v;maintain(p[x].y);

		}

		if(opt == 4)

		{

			x = rd();y = rd();

			makeroot(x);access(y);

			if(t[y].tot == xorsum)puts("YES");

			else puts("NO");

		}

	}

	return 0;

}