#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
", 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
", 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
", 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
", 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);
}
}