分析

因为我们要维护，删边，加边。所以我们考虑使用 。那么现在就是求问一条边是否被所有路径经过。所以我们考虑用子集异或。那么我们 之后，节点 的子树中的异或和必须等于 。所以我们还有维护虚子树。如果能分析到异或。这道题就不难了。

代码

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int N = 610000;
ull rnd[N],val[N],s1[N],s2[N];
int ch[N][2],L[N],R[N],fa[N],n,m;
bool r[N];
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x;
}
bool nroot(int x) {return ch[fa[x]][1] == x || ch[fa[x]][0] == x;}
void pushup(int x) {s1[x] = val[x] ^ s1[ch[x][1]] ^ s1[ch[x][0]] ^ s2[x];}
void pushr(int x) {swap(ch[x][1],ch[x][0]);r[x] ^= 1;}
void pushdown(int x) {
    if(r[x]) {
        if(ch[x][1]) pushr(ch[x][1]);
        if(ch[x][0]) pushr(ch[x][0]);
        r[x] = 0;
    }
}
void rotate(int x) {
    int y = fa[x],z = fa[y],k = (ch[y][1]==x),w = ch[x][!k];
    if(nroot(y)) ch[z][ch[z][1]==y] = x;ch[x][!k] = y;ch[y][k] = w;
    if(w) fa[w] = y;fa[x] = z;fa[y] = x;pushup(y);
}
void push(int x) {if(nroot(x)) push(fa[x]);pushdown(x);}
void splay(int x) {
    push(x);while(nroot(x)) {
        int y = fa[x],z = fa[y];if(nroot(y)) rotate(((ch[y][1]==x)^(ch[z][1]==y))?x:y);
        rotate(x);pushup(x);
    }
}
void access(int x) {
    for(int y = 0;x;x = fa[y=x]) {
        splay(x);s2[x] ^= s1[y] ^ s1[ch[x][1]];ch[x][1] = y;pushup(x);
    }
}
void makeroot(int x) {access(x);splay(x);pushr(x);}
void split(int x,int y) {makeroot(x);access(y);splay(y);}
void link(int x,int y) {split(x,y);fa[x] = y;s2[y] ^= s1[x];}
void cut(int x,int y) {split(x,y);ch[y][0] = fa[x] = 0;pushup(y);}
void ins(int x,ull w) {makeroot(x);val[x] ^= w;s1[x] ^= w;}
int main() {
    int top = 0,xzc;ull sum = 0;
    xzc = read();n = read();m = read();
    for(int i = 1;i < n;i++) {
        int a = read(),b = read();link(a,b);
    }
    while(m--) {
        int opt = read();
        if(opt == 1) {int x = read(),y = read(),u = read(),v = read();cut(x,y);link(u,v);}
        if(opt == 2) {
            top++;L[top] = read();R[top] = read();rnd[top] = 1ull * rand() * rand() * rand() * rand() * rand();
            ins(L[top],rnd[top]);ins(R[top],rnd[top]);sum ^= rnd[top];
        }
        if(opt == 3) {
            int id = read();ins(L[id],rnd[id]);ins(R[id],rnd[id]);sum ^= rnd[id];
        }
        if(opt == 4) {
            int x = read(),y = read();split(x,y);
            if(s1[x] ^ sum) puts("NO");else puts("YES");
        }
    }
}