洛谷P3950 部落冲突题解

题意：

在一个叫做 Travian 的世界里，生活着各个大大小小的部落。其中最为强大的是罗马、高卢和日耳曼。他们之间为了争夺资源和土地，进行了无数次的战斗。期间诞生了众多家喻户晓的英雄人物，也留下了许多可歌可泣的动人故事。

其中，在大大小小的部落之间，会有一些道路相连，这些道路是 Travian 世界里的重要枢纽，简单起见，你可以把这些部落与部落之间相连的道路看作一颗树，可见每条道路对于 Travian 世界的重要程度。有了这些道路，建筑工人就可以通过这些道路进行友好外交啦。

然而，事情并不会像想象的那样美好，由于资源的匮乏，相邻的部落（由一条道路相连的部落）之间经常会发生大大小小的冲突事件，更有甚者，会升级为部落之间的大型战争。

为了避免误伤，每当两个相邻的部落之间发生大型战争之时，这两个部落间的道路是不允许通行的，对于一些强大的部落，甚至能与多个相邻的部落同时开战，同样的，这些战争地带的道路十分危险，是不可通行的。

天下之势，分久必合，当两个部落经历了不打不相识的苦战之后，他们可以签订停战协议（暂时停战，以后依旧可能再次开战），这样，两个部落之间的道路又会重新恢复为可通行状态，建筑工人们又可以经过此地购买最新的大本营设计图纸来强大自己的部落了。

为了简单起见，我们把各大战争事件按发起的时间顺序依次编号（最先发起的战争编号就为 \(1\)，第二次战争编号就为 \(2\)，以此类推），当两个部落停战之时，则会直接告诉你这场战争的编号，然后这场战争就载入了史册，不复存在了，当然，这并不会影响到其他战争的编号。

建筑工人十分讨厌战争，因为战争，想从一个部落到另一个部落进行友好交流的建筑工人可能就此白跑一趟。所以，在他们出发之前，都会向你问问能不能到达他们想去的部落。

简单起见，你就是要处理下面三件事，所有的事件都是按照时间顺序给出的。

Q p q 从第 \(p\) 个部落出发的建筑工人想知道能否到达第 \(q\) 个部落了，你要回答的便是 Yes / No，注意大小写。

C p q 第 \(p\) 个部落与第 \(q\) 个部落开战了，保证他们一定是相邻的部落，且目前处于停战（未开战）状态。

U x 第 \(x\) 次发生的战争结束了，它将永远的被载入史册，不复存在（保证这个消息不会告诉你多次）

输入格式：

第一行两个数 \(n\) 和 \(m\)， \(n\) 代表了一共有 \(n\) 个部落，\(m\) 代表了以上三种事件发生的总数。

接下来的 \(n - 1\) 行，每行两个数 \(p, q\)，代表了第 \(p\) 个部落与第 \(q\) 个部落之间有一条道路相连。

接下来的 \(m\) 行，每行表示一件事，详见题目描述。

输出格式：

每行一个 Yes 或者 No，表示从第 \(p\) 个部落出发的建筑工人能否到达第 \(q\) 个部落。

数据范围：

\(1\leq n, m\leq 3\times10^5\)。

LCT 裸题，但是也是树剖裸题。这里讲树剖解法。

修改1就是询问路径边权和是否为 \(0\) ，修改2,3就是修改单条边。

很简单，我们维护每个节点和它父亲的连边即可。

时间复杂度 \(\mathcal{O}(n \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(3e5 + 15))
#define ls(at) ((at) << 1)
#define rs(at) ((at) << 1 | 1)

char op;
int n,m,pos=1,tot,head[N],p[N],q[N];
int dep[N],son[N],id[N],top[N],fa[N],sz[N],val[N * 4];
struct Edge { int u,v,next; } e[N * 2];
void addEdge(int u,int v) { e[++pos] = {u,v,head[u]}; head[u] = pos; }
void dfs(int u,int f,int d)
{
    dep[u] = d; fa[u] = f; sz[u] = 1; int mx = -1;
    for(int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].v; if(v == f) continue;
        dfs(v,u,d+1); sz[u] += sz[v]; if(sz[v] > mx) { mx = sz[v]; son[u] = v; }
    }
}
void dfs(int u,int ftop)
{
    static int tim = 0; top[u] = ftop; id[u] = ++tim;
    if(son[u]) dfs(son[u], ftop);
    for(int i = head[u]; i; i = e[i].next)
    { int v = e[i].v; if(v != fa[u] && v != son[u]) dfs(v,v); }
}
void Modify(int x, int k, int l = 1, int r = n, int at = 1)
{
    if(l == r) return val[at] = k, void(0);
    int mid = (l + r) >> 1;
    if(x <= mid) Modify(x, k, l, mid, ls(at));
    else Modify(x, k, mid + 1, r, rs(at));
    val[at] = val[ls(at)] + val[rs(at)];
}
int query(int nl,int nr,int l = 1, int r = n, int at = 1)
{
    // if(nl > nr) return 0;
    if(nl <= l && r <= nr) return val[at];
    int mid = (l + r) >> 1;
    if(nl > mid) return query(nl, nr, mid + 1, r, rs(at));
    if(nr <= mid) return query(nl, nr, l, mid, ls(at));
    return query(nl,nr,l,mid,ls(at)) + query(nl,nr,mid+1,r,rs(at));
}
int qRange(int x,int y)
{
    int res = 0; while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]]) swap(x,y);
        res += query(id[top[x]], id[x]); x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x,y);
    if(id[x] < id[y]) res += query(id[x] + 1, id[y]); return res;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i = 1, u, v; i < n; i++)
    { cin >> u >> v; addEdge(u,v); addEdge(v,u); }
    dfs(1,0,1); dfs(1,1);
    for(int i = 1, x,y,t; i <= m; i++)
    {
        // cout << "i = " << i << '\n';
        if(cin >> op, op == 'Q') {
            cin >> x >> y; cout << (qRange(x,y) == 0 ? "Yes\n" : "No\n");
        }else if(op == 'C') {
            ++tot; cin >> p[tot] >> q[tot]; x = p[tot]; y = q[tot];
            Modify(max(id[x], id[y]), 1);
        }else {
            cin >> t; Modify(max(id[p[t]], id[q[t]]), 0);
        }
    }
    return 0;
}