P3950部落冲突

题面

\(Solution:\)

法一：LCT裸题

又好想又好码，只不过常数太大。

法二：树链剖分

每次断边将该边权的值++，连边--，然后边权化点权(给儿子)，询问就查询从x到y的路径上的边权和，树状数组套树链剖分维护.

\(Source\)

// luogu-judger-enable-o2

#include <stdio.h>

#include <vector>

#include <assert.h>

#include <ctype.h>

#include <set>

#include <cstring>

using namespace std;

namespace io {

    char buf[1<<21], *pos = buf, *end = buf;

    inline char getc()

    { return pos == end && (end = (pos = buf) + fread(buf, 1, 1<<21, stdin), pos == end) ? EOF : *pos ++; }

    inline int rint() {

        register int x = 0, f = 1; register char c;

        while (!isdigit(c = getchar())) if (c == '-') f = -1;

        while (x = (x << 1) + (x << 3) + (c ^ 48), isdigit(c = getchar()));

        return x * f;

    }

    template<typename T>

        inline bool chkmin(T &x, T y) { return x > y ? (x = y, 0) : 1; }

    template<typename T>

        inline bool chkmax(T &x, T y) { return x < y ? (x = y, 0) : 1; }

#define debug(...) fprintf(stderr, __VA_ARGS__)

#define ____ debug("go")

#define rep(i, a, b) for (register int i = a; i <= b; ++ i)

#define dep(i, a, b) for (register int i = a; i >= b; -- i)

#define travel(i, u) for (register int i = head[u]; i; i = nxt[i])

#define mem(a, b) memset(a, b, sizeof a)

}

using io::rint;using io::chkmin;using io::chkmax;

const int N = 4e5 + 1;

int n, m;

int tot, ver[N<<1], head[N], nxt[N<<1];

void add(int u, int v)

{ ver[++tot] = v, nxt[tot] = head[u], head[u] = tot; }

int seg[N], size[N], top[N], son[N], cnt, fa[N], dep[N];

void DFS1(int x, int f) {

    fa[x] = f;

    size[x] = 1;

    dep[x] = dep[f] + 1;

    travel(i, x) {

        if (ver[i] == f) continue;

        DFS1(ver[i], x);

        size[x] += size[ver[i]];

        if (size[son[x]] < size[ver[i]]) son[x] = ver[i];

    }

}

void DFS2(int u, int topf) {

    seg[u] = ++cnt;

    top[u] = topf;

    if (son[u]) DFS2(son[u], topf);

    else return;

    travel(i, u) {

        if (ver[i] != fa[u] && ver[i] != son[u]) DFS2(ver[i], ver[i]);

    }

}

struct BIT {

    int s[N];

    void insert(int x, int c)

    { for (int i = x; i <= n; i += (i & -i)) s[i] += c; }

    int query(int x)

    { int res = 0; for (int i = x; i; i -= (i & -i)) res += s[i]; return res; }

} T;

vector<pair<int, int> > War;

int Query(int x, int y) {

    int ans = 0;

    while (top[x] != top[y]) {

        if (dep[top[x]] < dep[top[y]]) swap(x, y);//打挂的地方

        ans += T.query(seg[x]) - T.query(seg[top[x]] - 1);

        x = fa[top[x]];

    }

    if (dep[x] < dep[y]) swap(x, y);

    ans += T.query(seg[x]) - T.query(seg[y]);

    return ans;

}

int main() {

#ifndef ONLINE_JUDGE

    freopen("P3950.in", "r", stdin);

    freopen("P3950.out", "w", stdout);

#endif

    n = rint(); m = rint();

    for (int i = 1; i < n; ++ i) {

        int  u = rint(), v = rint();

        add(u, v); add(v, u);

    }

    DFS1(1, 0);

    DFS2(1, 1);

    char op[10]; int x, y;

    while (m --) {

        scanf("%s", op);

        if (op[0] == 'Q') {

            x = rint(), y = rint();

            if (Query(x, y)) puts("No");

            else puts("Yes");

        } else if (op[0] == 'U') {

            x = rint();

            x --;

            int u = War[x].first, v = War[x].second;

            if (seg[u] < seg[v]) swap(u, v);

            T.insert(seg[u], -1);

        } else {

            x = rint(), y = rint();

            if (seg[x] < seg[y]) swap(x, y);

            T.insert(seg[x], 1);

            War.push_back(make_pair(x, y));

        }

    }

}