求助树链剖分

Weight_of_the_Soul @ 2022-09-28 22:39:30

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;

int rd() {
    int x = 0, w = 1;
    char c = getchar();

    while(c < '0' || c > '9') {
        if(c == '-') w = -1;
        c = getchar();
    }

    while(c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = getchar();
    }

    return x * w;
}

const int N = 1e5 + 5;

int n, m;

struct Graph {
    int v, nxt;
}e[N << 1];

int lk[N], ltp;
int dfn[N], son[N], fa[N], siz[N], dep[N];
int rk[N], cnt;
int top[N];
int a[N];

void ins(int u, int v) {
    e[++ltp] = (Graph) {v, lk[u]};
    lk[u] = ltp;
}

void dfs1(int u) {
    siz[u] = 1;
    son[u] = -1;

    for(int i = lk[u]; i; i = e[i].nxt) {
        int v = e[i].v;
        if(!dep[v]) {
            dep[v] = dep[u] + 1;
            fa[v] = u;
            a[v] = 1;
            dfs1(v);

            siz[u] += siz[v];
            if(son[u] == -1 || siz[son[u]] < siz[v])
                son[u] = v;
        }
    }
}

void dfs2(int u, int t) {
    top[u] = t;
    ++cnt;
    dfn[u] = cnt;
    rk[cnt] = u;
    if(son[u] == -1) return ;
    dfs2(son[u], t);

    for(int i = lk[u]; i; i = e[i].nxt) {
        int v = e[i].v;
        if(v != son[u] && v != fa[u])
            dfs2(v, v);
    }
}

struct Tree {
    int l, r;
    int dat, tag;

    #define l(x) tr[x].l
    #define r(x) tr[x].r
    #define dat(x) tr[x].dat
    #define tag(x) tr[x].tag
    #define ls (p << 1)
    #define rs (ls | 1)

} tr[N << 3];

void build(int p, int l, int r) {
    l(p) = l, r(p) = r;
    if(l == r) {
        dat(p) = a[l];
        return ;
    }

    int mid = (r - l) / 2 + l;
    build(ls, l, mid), build(rs, mid + 1, r);
    dat(p) = dat(ls) + dat(rs);
}

void spr(int p) {
    if(tag(p) != 0) {
        tag(ls) += tag(p);
        tag(rs) += tag(p);
        dat(ls) += tag(p) * (r(ls) - l(ls) + 1);
        dat(rs) += tag(p) * (r(rs) - l(rs) + 1);
        tag(p) = 0;
    }
}

void change(int p, int l, int r, int del) {
    if(l <= l(p) && r >= r(p)) {
        dat(p) += del * (r(p) - l(p) + 1);
        tag(p) += del;
        return ;
    }

    spr(p);

    int mid = (r(p) - l(p)) / 2 + l(p);
    if(l <= mid) change(ls, l, r, del);
    if(r > mid) change(rs, l, r, del);

    dat(p) = dat(ls) + dat(rs);
}

int ask(int p, int l, int r) {
    if(l <= l(p) && r >= r(p)) return dat(p);

    spr(p);

    int res = 0;
    int mid = (r(p) - l(p)) / 2 + l(p);

    if(l <= mid) res += ask(ls, l, r);
    if(r > mid) res += ask(rs, l, r);

    dat(p) = dat(ls) + dat(rs);
    return res;
}

int main() {
    n = rd(), m = rd();
    for(int i = 1; i < n; ++i) {
        int u = rd(), v = rd();
        ins(u, v);
        ins(v, u);
    }

    dep[1] = 1;
    dfs1(1);
    dfs2(1, 1);

    build(1, 1, n);

    while(m--) {
        char opt;
        cin >> opt;
        int u = rd(), v = rd();
        if(opt == 'P') {
            while(top[u] != top[v]) {
                if(dep[top[u]] < dep[top[v]]) swap(u, v);
                change(1, dfn[top[u]], dfn[u], 1);
                u = fa[top[u]];
            }

            if(dep[u] > dep[v]) swap(u, v);
            change(1, dfn[u], dfn[v], 1);
            change(1, dfn[u], dfn[u], -1);
        } else {
            int ans = 0;
            while(top[u] != top[v]) {
                if(dep[top[u]] < dep[top[v]]) swap(u, v);
                ans += ask(1, dfn[top[u]], dfn[u]);
                u = fa[top[u]];
            }

            if(dep[u] > dep[v]) swap(u, v);
            ans += ask(1, dfn[u], dfn[v]);
            ans -= ask(1, dfn[u], dfn[u]);

            printf("%d\n", ans);
        }
    }
    return 0;
}

by Weight_of_the_Soul @ 2022-09-28 22:39:48

@Ptilopsis_w

by Ptilopsis_w @ 2022-09-29 05:44:41

建议remake(

by C_liar @ 2022-09-29 07:35:04

初始边权均为 0

by C_liar @ 2022-09-29 07:42:44

还有建树时，dat(p) = a[l] 是不对的，应该选(dfn 对应的节点的编号)的权值，个人习惯用 id 数组表示。

线段树上的节点相当于 dfn 值，直接这样会出问题（曾经因为这个wa了好多题），要写成 dat(p) = a[id[l]]。

by C_liar @ 2022-09-29 07:47:10

(哦，你用 rk 数组表示了

不管怎样吧，改好了。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;

int rd() {
    int x = 0, w = 1;
    char c = getchar();

    while(c < '0' || c > '9') {
        if(c == '-') w = -1;
        c = getchar();
    }

    while(c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = getchar();
    }

    return x * w;
}

const int N = 1e5 + 5;

int n, m;

struct Graph {
    int v, nxt;
}e[N << 1];

int lk[N], ltp;
int dfn[N], son[N], fa[N], siz[N], dep[N];
int rk[N], cnt;
int top[N];
int a[N];

void ins(int u, int v) {
    e[++ltp] = (Graph) {v, lk[u]};
    lk[u] = ltp;
}

void dfs1(int u) {
    siz[u] = 1;
    son[u] = -1;

    for(int i = lk[u]; i; i = e[i].nxt) {
        int v = e[i].v;
        if(!dep[v]) {
            dep[v] = dep[u] + 1;
            fa[v] = u;
            a[v] = 0;/**/
            dfs1(v);

            siz[u] += siz[v];
            if(son[u] == -1 || siz[son[u]] < siz[v])
                son[u] = v;
        }
    }
}

void dfs2(int u, int t) {
    top[u] = t;
    ++cnt;
    dfn[u] = cnt;
    rk[cnt] = u;
    if(son[u] == -1) return ;
    dfs2(son[u], t);

    for(int i = lk[u]; i; i = e[i].nxt) {
        int v = e[i].v;
        if(v != son[u] && v != fa[u])
            dfs2(v, v);
    }
}

struct Tree {
    int l, r;
    int dat, tag;

    #define l(x) tr[x].l
    #define r(x) tr[x].r
    #define dat(x) tr[x].dat
    #define tag(x) tr[x].tag
    #define ls (p << 1)
    #define rs (ls | 1)

} tr[N << 3];

void build(int p, int l, int r) {
    l(p) = l, r(p) = r;
    if(l == r) {
        dat(p) = a[rk[l]];/**/
        return ;
    }

    int mid = (r - l) / 2 + l;
    build(ls, l, mid), build(rs, mid + 1, r);
    dat(p) = dat(ls) + dat(rs);
}

void spr(int p) {
    if(tag(p) != 0) {
        tag(ls) += tag(p);
        tag(rs) += tag(p);
        dat(ls) += tag(p) * (r(ls) - l(ls) + 1);
        dat(rs) += tag(p) * (r(rs) - l(rs) + 1);
        tag(p) = 0;
    }
}

void change(int p, int l, int r, int del) {
    if(l <= l(p) && r >= r(p)) {
        dat(p) += del * (r(p) - l(p) + 1);
        tag(p) += del;
        return ;
    }

    spr(p);

    int mid = (r(p) - l(p)) / 2 + l(p);
    if(l <= mid) change(ls, l, r, del);
    if(r > mid) change(rs, l, r, del);

    dat(p) = dat(ls) + dat(rs);
}

int ask(int p, int l, int r) {
    if(l <= l(p) && r >= r(p)) return dat(p);

    spr(p);

    int res = 0;
    int mid = (r(p) - l(p)) / 2 + l(p);

    if(l <= mid) res += ask(ls, l, r);
    if(r > mid) res += ask(rs, l, r);

    dat(p) = dat(ls) + dat(rs);
    return res;
}

int main() {
    n = rd(), m = rd();
    for(int i = 1; i < n; ++i) {
        int u = rd(), v = rd();
        ins(u, v);
        ins(v, u);
    }

    dep[1] = 1;
    dfs1(1);
    dfs2(1, 1);

    build(1, 1, n);

    while(m--) {
        char opt;
        cin >> opt;
        int u = rd(), v = rd();
        if(opt == 'P') {
            while(top[u] != top[v]) {
                if(dep[top[u]] < dep[top[v]]) swap(u, v);
                change(1, dfn[top[u]], dfn[u], 1);
                u = fa[top[u]];
            }

            if(dep[u] > dep[v]) swap(u, v);
            change(1, dfn[u], dfn[v], 1);
            change(1, dfn[u], dfn[u], -1);
        } else {
            int ans = 0;
            while(top[u] != top[v]) {
                if(dep[top[u]] < dep[top[v]]) swap(u, v);
                ans += ask(1, dfn[top[u]], dfn[u]);
                u = fa[top[u]];
            }

            if(dep[u] > dep[v]) swap(u, v);
            ans += ask(1, dfn[u], dfn[v]);
            ans -= ask(1, dfn[u], dfn[u]);
            /*直接这样就行：ask(1, dfn[u]+1, dfn[v]) 不过线段树代码中要处理一些 l>r 的情况*/

            printf("%d\n", ans);
        }
    }
    return 0;
}

by C_liar @ 2022-09-29 07:48:46

QwQ,%东区大佬

by Weight_of_the_Soul @ 2022-09-29 22:04:24

@C_liar tql，thx