分析
因为我们要维护,删边,加边。所以我们考虑使用 。那么现在就是求问一条边是否被所有路径经过。所以我们考虑用子集异或。那么我们 之后,节点 的子树中的异或和必须等于 。所以我们还有维护虚子树。如果能分析到异或。这道题就不难了。
代码
#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"); } } }