-树链剖分-线段树- [洛谷 P3950]部落冲突

题目背景

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

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

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

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

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

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

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

题目描述

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

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

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

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

输入格式

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

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

接下来的 mmm 行，每行表示一件事，详见题目描述

输出格式

每行一个“Yes”或者“No”，表示从第 ppp 个部落出发的建筑工人能否到达第 q 个部落

输入样例

5 9
1 2
2 3
3 4
4 5
Q 1 4
C 2 1
C 4 3
Q 3 1
Q 1 5
U 1
U 2
C 4 3
Q 3 4

输出样例

Yes
No
No
No

Solution

这道题我第一眼看的是LCT，但后来想一想发现我不会LCT，就只好用树剖了。

我们可以把边权传到深度较深的点上，如果这条边断了，那么这条边的权加一，如果又连上了，那么就把边权减一。

查询时看看这条路径上的和是否为零就行了。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 600010
#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)
struct Edge {
    int v, nx;
}e[MAXN];
int head[MAXN], ecnt, n, m, x[MAXN], y[MAXN], dep[MAXN], si[MAXN], wt[MAXN], w[MAXN], _x, _y;
int fa[MAXN], top[MAXN], son[MAXN], cnt, r = 1, id[MAXN], ccnt;
char op;
void add(int f, int t) {
    e[++ecnt] = (Edge) {t, head[f]};
    head[f] = ecnt;
}
struct Segtree {
    int a[MAXN], b[MAXN << 2], tmax[MAXN << 2];
    void pd(int p) {
        b[p] = b[ls(p)] + b[rs(p)];
    }
    void build(int l, int r, int p) {
        if (l == r) {
            b[p] = a[l];
            return;
        }
        int m = (l + r) >> 1;
        build(l, m, ls(p));
        build(m + 1, r, rs(p));
        pd(p);
    }
    void updated(int x, int l, int r, int p, int k) {
        if (l == r) {
            b[p] += k;
            return;
        }
        int m = (l + r) >> 1;
        if (x <= m) updated(x, l, m, ls(p), k);
        else updated(x, m + 1, r, rs(p), k);
        pd(p);
    }
    int qsum(int x, int y, int l, int r, int p) {
        int s = 0;
        if (x <= l && y >= r) {
            return b[p];
        }
        int m = (l + r) >> 1;
        if (x <= m) s += qsum(x, y, l, m, ls(p));
        if (y > m) s += qsum(x, y, m + 1, r, rs(p));
        return s;
    }
} tree;
void dfs1(int u, int f, int deep) {
    dep[u] = deep;
    fa[u] = f;
    si[u] = 1;
    for (int i = head[u]; i; i = e[i].nx) {
        int to = e[i].v;
        if (to == f) continue;
        dfs1(to, u, deep + 1);
        si[u] += si[to];
        if (si[to] > si[son[u]]) son[u] = to;
    }
}
void dfs2(int u, int topf) {
    id[u] = ++cnt;
    wt[cnt] = w[u];
    top[u] = topf;
    if (!son[u]) return;
    dfs2(son[u], topf);
    for (int i = head[u]; i; i = e[i].nx) {
        int to = e[i].v;
        if (fa[u] == to || to == son[u]) continue;
        dfs2(to, to);
    }
}
inline int qrs(int x, int y) {
    int ans = 0;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) std::swap(x, y);
        ans += tree.qsum(id[top[x]], id[x], 1, n, 1);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) std::swap(x, y);
    ans += tree.qsum(id[x] + 1, id[y], 1, n, 1);
    return ans;
}
inline void change(int x, int k) {
    tree.updated(id[x], 1, n, 1, k);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i < n; i++) {
        scanf("%d%d", &_x, &_y);
        add(_x, _y);
        add(_y, _x);
    }
    dfs1(r, -1, 1);
    dfs2(r, r);
    while (m--) {
        std::cin >> op;
        if (op == 'C') {
            ccnt++;
            scanf("%d%d", &x[ccnt], &y[ccnt]);
            if (dep[x[ccnt]] < dep[y[ccnt]]) std::swap(x[ccnt], y[ccnt]);
            change(x[ccnt], 1);
        }
        if (op == 'Q') {
            scanf("%d%d", &_x, &_y);
            if (qrs(_x, _y)) {
                puts("No");
            }
            else {
                puts("Yes");
            }
        }
        if (op == 'U') {
            scanf("%d", &_x);
            change(x[_x], -1);
        }
    }
}