UOJ 题求助，玄关

Gold14526 @ 2025-07-28 10:25:29

by bloxd @ 2025-07-28 10:29:25

@Gold14526 我没号，题目发一下

by Gold14526 @ 2025-07-28 10:30:55

@bloxd 可以看题目链接吗 https://uoj.ac/problem/207

by bloxd @ 2025-07-28 10:33:35

@Gold 给个代码，来调

by Gold14526 @ 2025-07-28 10:33:56

@bloxd

#include<bits/stdc++.h>
#define cint const int
#define uint unsigned int
#define cuint const unsigned int
#define ll long long
#define cll const long long
#define ull unsigned long long
#define cull const unsigned long long
#define sh short
#define csh const short
#define ush unsigned short
#define cush const unsigned short
using namespace std;
int read()
{
    int num=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        num=(num<<1)+(num<<3)+(ch-'0');
        ch=getchar();
    }
    return num;
}
void print(cint x)
{
    if(x<10)
    {
        putchar(x+'0');
        return;
    }
    print(x/10);
    putchar(x%10+'0');
}
void princh(cint x,const char ch)
{
    print(x);
    putchar(ch);
}
mt19937_64 mt(chrono::system_clock().now().time_since_epoch().count());
cint N=1e5,Q=3e5;
ull val[N+1];
struct Link_Cut_Tree{
    int f[N+1];
    struct node{
        int son[2];
        ull xs,xi;
        bool tag;
    }t[N+1];
    inline bool notroot(cint x)
    {
        return (t[f[x]].son[0]==x||t[f[x]].son[1]==x);
    }
    inline void rev(cint p)
    {
        swap(t[p].son[0],t[p].son[1]);
        t[p].tag^=1;
    }
    inline void push_up(cint p)
    {
        t[p].xs=t[t[p].son[0]].xs^t[t[p].son[1]].xs^t[p].xi^val[p];
    }
    inline void push_down(cint p)
    {
        if(t[p].tag)
        {
            rev(t[p].son[0]);
            rev(t[p].son[1]);
            t[p].tag=0;
        }
    }
    void rotate(cint x)
    {
        cint y=f[x],z=f[y],p=(t[y].son[1]==x),q=(t[z].son[1]==y),w=t[x].son[!p];
        if(notroot(y))
        {
            t[z].son[q]=x;
        }
        t[x].son[!p]=y;
        t[y].son[p]=w;
        if(w)
        {
            f[w]=y;
        }
        f[y]=x;
        f[x]=z;
        push_up(y);
    }
    void rotate2(cint x)
    {
        cint y=f[x],z=f[y];
        if(notroot(y))
        {
            rotate((t[y].son[0]==x)^(t[z].son[0]==y)?x:y);
        }
        rotate(x);
    }
    void push_all(cint x)
    {
        if(notroot(x))push_all(f[x]);
        push_down(x);
    }
    void splay(cint x)
    {
        push_all(x);
        while(notroot(x))
        {
            rotate2(x);
        }
        push_up(x);
    }
    void access(int x)
    {
        for(int y=0;x;y=x,x=f[x])
        {
            splay(x);
            t[x].xi^=t[t[x].son[1]].xs^t[y].xs;
            t[x].son[1]=y;
            push_up(x);
        }
    }
    void make_root(cint x)
    {
        access(x);
        splay(x);
        rev(x);
    }
    int find_root(int x)
    {
        access(x);
        splay(x);
        while(t[x].son[0])
        {
            push_down(x);
            x=t[x].son[0];
        }
        splay(x);
        return x;
    }
    void link(cint x,cint y)
    {
        make_root(x);
        access(y);
        f[x]=y;
        t[y].xi^=t[x].xs;
        push_up(y);
    }
    void cut(cint x,cint y)
    {
        make_root(x);
        access(y);
        splay(x);
        f[y]=t[x].son[1]=0;
        push_up(x);
    }
    ull ask(cint x,cint y)
    {
        make_root(x);
        access(y);
        splay(y);
        return (t[y].xs^t[t[y].son[0]].xs);
    }
}T;
int n,q;
struct dat{
    int x,y;
    ull w;
};
vector<dat>S;
ull xsum;
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    read();
    n=read();
    q=read();
    for(int i=1;i<n;++i)
    {
        T.link(read(),read());
    }
    S.push_back(dat{0,0,0});
    while(q--)
    {
        cint op=read();
        if(op==1)
        {
            T.cut(read(),read());
            T.link(read(),read());
        }
        else if(op==2)
        {
            cint x=read(),y=read();
            cull w=mt();
//          printf(">%llu\n",w);
            T.make_root(x);
            val[x]^=w;
            T.push_up(x);
            T.make_root(y);
            val[y]^=w;
            T.push_up(y);
            xsum^=w;
            S.push_back(dat{x,y,w});
        }
        else if(op==3)
        {
            cint p=read();
            T.make_root(S[p].x);
            val[S[p].x]^=S[p].w;
            T.push_up(S[p].x);
            T.make_root(S[p].y);
            val[S[p].y]^=S[p].w;
            T.push_up(S[p].y);
            xsum^=S[p].w;
        }
        else
        {
            cint x=read(),y=read();
//          printf(">%llu s=%llu\n",T.ask(x,y),xsum);
            puts((T.ask(x,y)==xsum?"YES":"NO"));
        }
    }
    return 0;
}
/*
0
5 7
1 2
1 3
2 4
1 5
2 1 5
1 1 5 2 5
4 2 5
2 1 4
4 2 5
3 1
4 2 4
*/

by Gold14526 @ 2025-07-28 10:37:22

@bloxd 只有含有 1 操作的数据会出错。

by bloxd @ 2025-07-28 10:41:54

link/cut 后未正确更新虚子树信息

void link(cint x, cint y) {
    make_root(x);
    access(y), splay(y);
    f[x] = y, t[y].xi ^= t[x].xs;
    push_up(y);
@[Gold](luogu://user/20905)
}

by bloxd @ 2025-07-28 10:43:30

@Gold14526

by Gold14526 @ 2025-07-28 10:43:54

@bloxd 感谢，已关注。