题目地址：UOJ：共价大爷游长沙 – 题目 – Universal Online Judge

题目描述

火车司机出秦川，跳蚤国王下江南，共价大爷游长沙。每个周末，勤劳的共价大爷都会开车游历长沙市。
长沙市的交通线路可以抽象成为一个 n 个点 n-1 条边的无向图，点编号为 1 到 n，任意两点间均存在恰好一条路径，显然两个点之间最多也只会有一条边相连。有一个包含一些点对 (x,y) 的可重集合 S，共价大爷的旅行路线是这样确定的：每次他会选择 S 中的某一对点 (x,y)，并从 x 出发沿着唯一路径到达 y。
小L是共价大爷的脑残粉，为了见到共价大爷的尊容，小L决定守在这张图的某条边上等待共价大爷的到来。为了保证一定能见到他，显然小L必须选择共价大爷一定会经过的边——也就是所有共价大爷可能选择的路径都经过的边。
现在小L想知道，如果他守在某一条边，是否一定能见到共价大爷。
然而长沙市总是不断的施工，也就是说，可能某个时刻某条边会断开，同时这个时刻一定也有某条新边会出现，且任意时刻图都满足任意两点间均存在恰好一条路径的条件。注意断开的边有可能和加入的新边连接着相同的两个端点。共价大爷的兴趣也会不断变化，所以S也会不断加入新点对或者删除原有的点对。当然，小L也有可能在任何时候向你提出守在某一条边是否一定能见到共价大爷的问题。你能回答小L的所有问题吗？

输入输出格式

输入格式：
输入的第一行包含一个整数 id，表示测试数据编号，如第一组数据的id=1，样例数据的 id 可以忽略。hack数据中的 id 必须为 0 到 10 之间的整数。hack数据中id的值和数据类型没有任何关系。
输入的第二行包含两个整数 n,m，分别表示图中的点数，以及接下来会发生的事件数，事件的定义下文中会有描述。初始时 S 为空。
接下来 n-1 行，每行两个正整数 x,y，表示点 x 和点 y 之间有一条无向边。
接下来 m 行，每行描述一个事件，每行的第一个数 type 表示事件的类型。
若type=1，那么接下来有四个正整数x,y,u,v，表示先删除连接点x和点y的无向边，保证存在这样的无向边，然后加入一条连接点u和点v的无向边，保证操作后的图仍然满足题中所述条件。
若type=2，那么接下来有两个正整数 x,y，表示在 S 中加入点对 (x,y)。
若type=3，那么接下来有一个正整数 x，表示删除第 x 个加入 S 中的点对，即在第 x 个 type=2 的事件中加入 S 中的点对，保证这个点对存在且仍然在 S 中。
若type=4，那么接下来有两个正整数 x,y，表示小L询问守在连接点 x 和点 y 的边上是否一定能见到共价大爷，保证存在这样的无向边且此时 S 不为空。

输出格式：
对于每个小L的询问，输出“YES”或者“NO”（均不含引号）表示小L一定能或者不一定能见到共价大爷。

输入输出样例

输入样例#1：

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

输出样例#1：

YES
NO
YES

题解

参考资料：【uoj207】 共价大爷游长沙 – MashiroSky – 博客园，感谢原作者。
这里我们使用异或标记链信息，使用异或的好处是便于处理子树信息，且操作可逆。
我们考虑如果一条边满足要求，那么所有的链端点肯定分布于这条边端点的两个子树中。既然如此，我们可以在链端点设置随机权值，并且用LCT来维护树的形态与子树的权值异或和。每次查询查这条边任意一端的子树异或和是否等于所有链权值的异或和。
注意LCT中子树信息不仅要维护Splay上的子树信息，还要维护轻边所连接的儿子信息，因此涉及到轻边重边变化的操作，如access、link、cut等，需要维护好轻儿子信息。维护轻儿子信息需要对LCT各种操作对树形态的影响十分熟悉，存在一定难度。代码中，我用val来表示该节点与所有轻儿子子树的异或和，sum表示所在Splay子树的val值异或和。查询时，Splay中只有u、v两个点，因此v的轻儿子子树加上v就是v所在子树，查val即可。

代码

// Code by KSkun, 2018/3
#include <cstdio>
#include <cstdlib>
#include <ctime>

#include <algorithm>

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline int readint() {
    register int res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 300005, INF = 1e9;

struct LCTNode {
    int ch[2], fa, val, sum;
    bool rev;
} lct[MAXN];

inline bool isleft(int p) {
    return lct[lct[p].fa].ch[0] == p;
}

inline bool isroot(int p) {
    register int fa = lct[p].fa;
    return lct[fa].ch[0] != p && lct[fa].ch[1] != p;
}

inline void update(int p) {
    register int ls = lct[p].ch[0], rs = lct[p].ch[1];
    lct[p].sum = lct[p].val ^ lct[ls].sum ^ lct[rs].sum;
}

inline void reverse(int p) {
    std::swap(lct[p].ch[0], lct[p].ch[1]);
    lct[p].rev ^= 1;
}

inline void pushdown(int p) {
    register int ls = lct[p].ch[0], rs = lct[p].ch[1];
    if(lct[p].rev) {
        if(ls) reverse(ls);
        if(rs) reverse(rs);
        lct[p].rev ^= 1;
    }
}

int sta[MAXN], stop;

inline void pushto(int p) {
    stop = 0;
    while(!isroot(p)) {
        sta[stop++] = p;
        p = lct[p].fa;
    }
    pushdown(p);
    while(stop) {
        pushdown(sta[--stop]);
    }
}

inline void rotate(int p) {
    register bool t = !isleft(p); register int fa = lct[p].fa, ffa = lct[fa].fa;
    lct[p].fa = ffa; if(!isroot(fa)) lct[ffa].ch[!isleft(fa)] = p;
    lct[fa].ch[t] = lct[p].ch[!t]; lct[lct[fa].ch[t]].fa = fa;
    lct[p].ch[!t] = fa; lct[fa].fa = p;
    update(fa);
}

inline void splay(int p) {
    pushto(p);
    for(register int fa = lct[p].fa; !isroot(p); rotate(p), fa = lct[p].fa) {
        if(!isroot(fa)) rotate(isleft(fa) == isleft(p) ? fa : p);
    }
    update(p);
}

inline void access(int p) {
    for(register int q = 0; p; q = p, p = lct[p].fa) {
        splay(p);
        lct[p].val ^= lct[lct[p].ch[1]].sum;
        lct[p].ch[1] = q;
        lct[p].val ^= lct[lct[p].ch[1]].sum;
        update(p);
    }
}

inline void makert(int p) {
    access(p);
    splay(p);
    reverse(p);
}

inline int findrt(int p) {
    access(p);
    splay(p);
    while(lct[p].ch[0]) p = lct[p].ch[0];
    return p;
}

inline void split(int u, int v) {
    makert(u);
    access(v);
    splay(v);
}

inline void link(int u, int v) {
    split(u, v);
    lct[u].fa = v;
    lct[v].val ^= lct[u].sum;
    update(v);
}

inline void cut(int u, int v) {
    split(u, v);
    if(lct[v].ch[0] != u || lct[lct[v].ch[0]].ch[1]) return;
    lct[u].fa = lct[v].ch[0] = 0;
    update(v);
}

inline int query(int u, int v) {
    makert(u);
    access(v);
    return lct[v].val;
}

inline void modify(int u, int w) {
    access(u);
    splay(u);
    lct[u].val ^= w;
    update(u);
}

int n, m, op, x, y, w, u, v, all;

struct Edge {
    int u, v, w;
} edge[MAXN];
int tot;

int main() {
    srand(time(NULL));
    readint(); n = readint(); m = readint();
    for(int i = 1; i < n; i++) {
        u = readint(); v = readint();
        link(u, v);
    }
    while(m--) {
        op = readint();
        switch(op) {
        case 1:
            x = readint(); y = readint(); u = readint(); v = readint();
            cut(x, y);
            link(u, v);
            break;
        case 2:
            x = readint(); y = readint(); w = rand();
            edge[++tot] = Edge {x, y, w};
            modify(x, w);
            modify(y, w);
            all ^= w;
            break;
        case 3:
            x = readint();
            modify(edge[x].u, edge[x].w);
            modify(edge[x].v, edge[x].w);
            all ^= edge[x].w;
            break;
        case 4:
            x = readint(); y = readint();
            puts(query(x, y) == all ? "YES" : "NO");
        }
    }
    return 0;
}