#207. 共价大爷游长沙

题意：一棵树，支持加边删边，加入点对，删除点对，询问所有点对是否经过一条边

---

一开始一直想在边权上做文章，或者从连通分量角度考虑，比较接近正解了，但是没想到给点对分配权值所以没做出来

题解的后两种做法说的很清楚了，我用了第二种因为我没写过lct维护子树信息

给点对分配权值后，我们只要看一条边的权值是否等于当前异或和就行了

加边删边时，把删除边\((u,v)\)的权值异或到之后\((u,v)\)的路径上，巧妙利用了异或的自反性，和wc那道xor很像

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <map>

using namespace std;

typedef long long ll;

#define lc t[x].ch[0]

#define rc t[x].ch[1]

#define pa t[x].fa

const int N = 4e5+5;

inline int read(){

	char c=getchar(); int x=0,f=1;

	while(c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();}

	while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();}

	return x*f;

}

int n, m, type, x, y, u, v, tot, cnt, now;

map<int, int> eid[N];

struct pai{int x, y, val;} s[N];

namespace lct {

	struct meow{ int ch[2], fa, rev, val, tag; } t[N];

	inline int wh(int x) {return t[pa].ch[1] == x;}

	inline bool isr(int x) {return t[pa].ch[0] != x && t[pa].ch[1] != x;}

	inline void rever(int x) {t[x].rev ^= 1; swap(lc, rc);}

	inline void paint(int x, int v) {t[x].tag ^= v; t[x].val ^= v;}

	inline void pushdn(int x) {

		if(t[x].rev) {

			if(lc) rever(lc);

			if(rc) rever(rc);

			t[x].rev = 0;

		}

		if(t[x].tag) {

			if(lc) paint(lc, t[x].tag);

			if(rc) paint(rc, t[x].tag);

			t[x].tag = 0;

		}

	}

	inline void pd(int x) {if(!isr(x)) pd(pa); pushdn(x);}

	inline void update(int x) {}

	inline void rotate(int x) {

		int f = t[x].fa, g = t[f].fa, c = wh(x);

		if(!isr(f)) t[g].ch[wh(f)] = x; t[x].fa = g;

		t[f].ch[c] = t[x].ch[c^1]; t[ t[f].ch[c] ].fa = f;

		t[x].ch[c^1] = f; t[f].fa = x;

		update(f); update(x);

	}

	inline void splay(int x) {

		pd(x);

		for(; !isr(x); rotate(x))

			if(!isr(pa)) rotate(wh(x) == wh(pa) ? pa : x);

	}

	inline void access(int x) {

		for(int y=0; x; y=x, x=pa)

			splay(x), rc=y, update(x);

	}

	inline void maker(int x) { access(x); splay(x); rever(x);}

	inline void link(int x, int y) { maker(x); t[x].fa = y; }

	inline void cut(int x, int y) {

		maker(x); access(y); splay(y);

		t[x].fa = t[y].ch[0] = 0; update(y);

	}

	inline void split(int x, int y) { maker(x), access(y); splay(y); }

} using namespace lct;

void rep() {

	x=read(); y=read(); if(x > y) swap(x, y);

	int id = eid[x][y]; pd(id);

	int val = t[id].val; //printf("val %d  %d\n", id, val);

	cut(id, x); cut(id, y);

	int _x = x, _y = y;

	x=read(); y=read(); if(x > y) swap(x, y);

	eid[x][y] = ++cnt;

	link(cnt, x); link(cnt, y);

	split(_x, _y); paint(_y, val);

}

inline int ran() {return rand()+1;}

void add(int x, int y) {

	s[++tot] = (pai){x, y, ran()};

	split(x, y); paint(y, s[tot].val);

	now ^= s[tot].val; //printf("add %d (%d, %d)  %d  %d\n", tot, x, y, s[tot].val, now);

}

void del(int id) {

	int x = s[id].x, y = s[id].y;

	split(x, y); paint(y, s[id].val);

	now ^= s[id].val; //printf("del %d  (%d, %d)  %d  %d\n", id, s[id].x, s[id].y, s[id].val, now);

}

void que(int x, int y) {

	if(x > y) swap(x, y);

	int id = eid[x][y]; pd(id); //printf("hi %d  %d   now  %d\n", id, t[id].val, now);

	puts(t[id].val == now ? "YES" : "NO");

}

int main() {

	freopen("in", "r", stdin);

	freopen("out", "w", stdout);

	srand(317);

	int qwq=read(); qwq++;

	n=read(); m=read(); cnt=n;

	for(int i=1; i<n; i++) {

		u=read(), v=read();

		if(u > v) swap(u, v);

		eid[u][v] = ++cnt;

		link(cnt, u); link(cnt, v);

	}

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

		type=read();

		if(type == 1) rep();

		else if(type == 2) x=read(), y=read(), add(x, y);

		else if(type == 3) x=read(), del(x);

		else x=read(), y=read(), que(x, y);

	}

}