共价大爷游长沙

发表于 2025-07-27 更新于 2025-03-04 本文字数： 2.5k 阅读时长 ≈ 2 分钟

来自我的口胡记录。

确实是一道好题，讲详细点。
首先有一种显然的暴力，即暴力增加路径、改变路径、查询答案，出题人良心地给了 $ 10 $ 分。
若无加减边的操作和删除的操作，那么我们可以维护当前的可行路径，每次可以用 $ O(logn) $ 或者 $ O(1) $ 时间进行树上路径求交以及判断一条边是否在路径上。
如果没有加边删边操作，那么我们可以用动态树或者树链剖分等支持链修改单点询问的结构，维护每个点被路径经过的次数，每次看看询问边的两个端点是否都被经过了 $ |S| $ 次。
对于 $ |S| \leq 10 $ 的数据，我们可以每次询问的时候进行和算法三类似的操作，每次暴力加入所有路径维护每个点被经过的次数再用同样的方法询问，期望得分 $ 20 $ 分。
然后是正解。我们难以维护的是两点之间的动态路径，加减边令人头大。考虑树上差分，在 $ lca $ 处减两倍的值~~然而动态树并没有lca~~，考虑异或，异或两个相同的值相当于没操作。如此将端点都异或一个相同的随机数即可，同时统计所有路径的变量也要异或相同的数。 $ LCT $ 维护即可。
~~然而我打了代码。~~

#include<bits/stdc++.h>
#define lc ch[u][0]
#define rc ch[u][1]
using namespace std;
const int N=100010;
int n,m,ans;
int fa[N],ch[N][2],v[N],s[N],sta[N];
bool lz[N];
int tx[N*5],ty[N*5],w[N*5],cnt=0;

int Rand() { return (rand()<<15)+rand(); }
inline bool nroot(const int u) { return ch[fa[u]][0]==u||ch[fa[u]][1]==u; }
inline void pushup(const int u) { s[u]=s[lc]^s[rc]^v[u]; }
void pushdown(int u) { if(lz[u]) swap(lc,rc),lz[lc]^=1,lz[rc]^=1,lz[u]=0; }
void rotate(int u) {
    int y=fa[u],z=fa[y],k=ch[y][1]==u,w=ch[u][k^1];
    if(nroot(y)) ch[z][ch[z][1]==y]=u; ch[y][k]=w,ch[u][k^1]=y;
    if(w) fa[w]=y; fa[y]=u,fa[u]=z;
    pushup(y),pushup(u);
}
void splay(int u) {
    int y=u,z,top=1;sta[top]=y;while(nroot(y)) sta[++top]=y=fa[y];
    while(top) pushdown(sta[top--]);
    for(;nroot(u);rotate(u)) {
        y=fa[u],z=fa[y]; if(nroot(y)) rotate((ch[y][0]==u)^(ch[z][0]==y)? u:y);
    }
}
void access(int u) {
    for(int y=0;u;u=fa[y=u]) splay(u),v[u]^=s[rc],rc=y,v[u]^=s[y],pushup(u);
}
void makeroot(int u) { access(u),splay(u),lz[u]^=1; }
void split(int x,int y) { makeroot(x),access(y),splay(y); }
void lnk(int x,int y) { makeroot(x),makeroot(y),fa[x]=y,v[y]^=s[x]; }
void cut(int x,int y) { split(x,y),fa[x]=ch[y][0]=0,pushup(y); }
void mdy(int x,int w) { makeroot(x),v[x]^=w,s[x]^=w; }
int main() {
    srand((unsigned int)time(NULL));
    scanf("%d",&n),scanf("%d%d",&n,&m);
    for(int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),lnk(x,y);
    int opt,x,y;
    for(;m;--m) {
        scanf("%d",&opt);
        if(opt==1)
            scanf("%d%d",&x,&y),cut(x,y),scanf("%d%d",&x,&y),lnk(x,y);
        else if(opt==2) {
            ++cnt,scanf("%d%d",&tx[cnt],&ty[cnt]),w[cnt]=Rand();
            ans^=w[cnt],mdy(tx[cnt],w[cnt]),mdy(ty[cnt],w[cnt]);
        }
        else if(opt==3)
            scanf("%d",&x),ans^=w[x],mdy(tx[x],w[x]),mdy(ty[x],w[x]);
        else
            scanf("%d%d",&x,&y),split(x,y),puts((v[y]==ans)? "YES":"NO");
    }
    return 0;
}