树剖八题

发布于 2019-10-31  229 次阅读


你没有看错,这次是一个八题系列:joy:

不含树剖算法详解,供已经会树剖的同学刷题食用

Luogu3384 【模板】树链剖分

树剖的模板题,包含了树剖题基本会涉及到的所有操作。

如果是询问一条链的长度,需要暴跳求和。

其他的信息都用线段树维护即可(区间修改、询问)

Code

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int SIZE = 100000 + 5;

int n, m, r, Mod, num, root;
int head[SIZE], size[SIZE], son[SIZE], fa[SIZE], depth[SIZE], Rank[SIZE], top[SIZE], id[SIZE], a[SIZE];

struct Segment_tree {
    int l, r, lson, rson, tag, sum;
} tree[SIZE << 2];

struct node {
    int to, Next;
} edge[SIZE << 1];

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

inline void Addedge(int x, int y)
{
    edge[++num].to = y;
    edge[num].Next = head[x];
    head[x] = num;
}

inline void DFS1(int u)
{
    size[u] = 1, depth[u] = depth[fa[u]] + 1;
    for (int i = head[u]; i; i = edge[i].Next) {
        int v = edge[i].to;
        if (v == fa[u]) continue;
        fa[v] = u;
        DFS1(v);
        size[u] += size[v];
        if (size[son[u]] < size[v]) son[u] = v;
    }
}

inline void DFS2(int u, int TOP)
{
    top[u] = TOP, id[u] = ++num, Rank[num] = u;
    if (son[u]) DFS2(son[u], TOP);
    for (int i = head[u]; i; i = edge[i].Next) {
        int v = edge[i].to;
        if (v != fa[u] && v != son[u]) DFS2(v, v);
    }
}

inline int pos(int x) { return tree[x].r - tree[x].l + 1; }

inline void Pushup(int x) { tree[x].sum = (tree[tree[x].lson].sum + tree[tree[x].rson].sum) % Mod; }

inline void Pushdown(int x)
{
    if (tree[x].tag) {
        int lson = tree[x].lson, rson = tree[x].rson, tag = tree[x].tag;
        (tree[lson].tag += tag) %= Mod, (tree[rson].tag += tag) %= Mod;
        (tree[lson].sum += tag * pos(lson)) %= Mod, (tree[rson].sum += tag * pos(rson)) %= Mod;
        tree[x].tag = 0;
    }
}

inline void Build(int l, int r, int x)
{
    if (l == r) {
        tree[x].sum = a[Rank[l]], tree[x].l = tree[x].r = l;
        return;
    }
    tree[x].lson = num++, tree[x].rson = num++;
    int Mid = (l + r) >> 1;
    Build(l, Mid, tree[x].lson), Build(Mid + 1, r, tree[x].rson);
    tree[x].l = tree[tree[x].lson].l, tree[x].r = tree[tree[x].rson].r;
    Pushup(x);
}

inline void Change(int l, int r, int val, int x)
{
    if (tree[x].l >= l && tree[x].r <= r) {
        (tree[x].tag += val) %= Mod, (tree[x].sum += pos(x) * val) %= Mod;
        return;
    }
    Pushdown(x);
    int Mid = (tree[x].l + tree[x].r) >> 1;
    if (Mid >= l) Change(l, r, val, tree[x].lson);
    if (Mid < r) Change(l, r, val, tree[x].rson);
    Pushup(x);
}

inline int Query(int l, int r, int x)
{
    if (tree[x].l >= l && tree[x].r <= r)
        return tree[x].sum;
    Pushdown(x);
    int Mid = (tree[x].l + tree[x].r) >> 1, ans = 0;
    if (Mid >= l) ans += Query(l, r, tree[x].lson);
    if (Mid < r) ans += Query(l, r, tree[x].rson);
    return ans % Mod;
}

inline int Get_sum(int u, int v)
{

    int ret = 0;
    while (top[u] != top[v]) {
        if (depth[top[u]] < depth[top[v]]) std::swap(u, v);
        (ret += Query(id[top[u]], id[u], root)) %= Mod;
        u = fa[top[u]];
    }
    if (id[u] > id[v]) std::swap(u, v);
    return (ret + Query(id[u], id[v], root)) % Mod;
}

inline void Update(int u, int v, int val)
{
    while (top[u] != top[v]) {
        if (depth[top[u]] < depth[top[v]]) std::swap(u, v);
        Change(id[top[u]], id[u], val, root);
        u = fa[top[u]];
    }
    if (id[u] > id[v]) std::swap(u, v);
    Change(id[u], id[v], val, root);
}

signed main()
{
    int u, v;   
    n = read(), m = read(), r = read(), Mod = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    for (int i = 1; i < n; i++) {
        u = read(), v = read();
        Addedge(u, v);
        Addedge(v, u);
    }
    num = 0;
    DFS1(r); DFS2(r, r);
    num = 0;
    Build(1, n, root = num++);
    int opt, x, y, k;
    while (m--) {
        opt = read();
        if (opt == 1) {
            x = read(), y = read(), k = read();
            Update(x, y, k);
        }
        if (opt == 2) {
            x = read(), y = read();
            printf("%lld\n", Get_sum(x, y));
        }
        if (opt == 3) {
            x = read(), y = read();
            Change(id[x], id[x] + size[x] - 1, y, root);
        }
        if (opt == 4) {
            x = read();
            printf("%lld\n", Query(id[x], id[x] + size[x] - 1, root));
        }
    }
    return 0;
}

Luogu2146 [NOI2015]软件包管理器

树剖模板题,看清楚题意就会做。

按照依赖关系建树以后,它的删除操作就是把它的子树全部清零,安装软件就是该节点到根节点的路径变为1

回答的时候先记住修改前线段树root的值,在与修改后的作差即可。

Code

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 100000 + 5;

int n, Q, num;
int head[SIZE], son[SIZE], fa[SIZE], depth[SIZE], id[SIZE], top[SIZE], size[SIZE];

struct node {
    int to, Next;
} edge[SIZE << 1];

struct Segment_tree {
    int sum, tag, l, r, lson, rson;
} tree[SIZE << 2];

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

inline void Addedge(int x, int y)
{
    edge[++num].to = y;
    edge[num].Next = head[x];
    head[x] = num;
}

inline void DFS1(int u)
{
    size[u] = 1, depth[u] = depth[fa[u]] + 1;
    for (int i = head[u]; i; i = edge[i].Next) {
        int v = edge[i].to;
        if (v == fa[u]) continue;
        fa[v] = u;
        DFS1(v);
        size[u] += size[v];
        if (size[son[u]] < size[v]) son[u] = v;
    }
}

inline void DFS2(int u, int TOP)
{
    id[u] = ++num, top[u] = TOP;
    if (!son[u]) return;
    DFS2(son[u], TOP);
    for (int i = head[u]; i; i = edge[i].Next) {
        int v = edge[i].to;
        if (v != son[u] && v != fa[u]) DFS2(v, v);
    }
}

inline void Build(int x, int l, int r)
{
    tree[x].l = l, tree[x].r = r, tree[x].sum = 0, tree[x].tag = -1;
    if (l == r) return;
    int mid = (l + r) >> 1;
    Build(x << 1, l, mid); Build(x << 1 | 1, mid + 1, r);
    return;
}

inline void Pushdown(int x)
{
    tree[x << 1].sum = (tree[x << 1].r - tree[x << 1].l + 1) * tree[x].tag;
    tree[x << 1 | 1].sum = (tree[x << 1 | 1].r - tree[x << 1 | 1].l + 1) * tree[x].tag;
    tree[x << 1].tag = tree[x << 1| 1].tag = tree[x].tag;
    tree[x].tag = -1; 
}

inline int Query(int x,int l,int r)
{
    if (tree[x].r <= r && tree[x].l >= l) return tree[x].sum;
    if (tree[x].tag != -1) Pushdown(x);
    return Query(x << 1, l, r) + Query(x << 1 | 1, l, r);
}

inline void Change(int x,int l,int r,int val)
{
    if (tree[x].r < l || tree[x].l > r) return;
    if (tree[x].r <= r && tree[x].l >= l) {
        tree[x].sum = (tree[x].r - tree[x].l + 1) * val;
        tree[x].tag = val;
        return;
    }
    if(tree[x].tag != -1) Pushdown(x);
    Change(x << 1, l, r, val); Change(x << 1 | 1, l, r, val);
    tree[x].sum = tree[x << 1].sum + tree[x << 1 | 1].sum;
    return;
}
inline void Update(int u, int v, int val)
{
    while (top[u] != top[v])
    {
        if (depth[top[u]] < depth[top[v]]) std::swap(u,v);
        Change(1, id[top[u]], id[u], val);
        u = fa[top[u]];
    }
    if (depth[u] > depth[v]) std::swap(u,v);
    Change(1, id[u], id[v], val);
    return;
}

int main()
{
    n = read();
    for (int i = 2; i <= n; i++) {
        int u = read() + 1;
        Addedge(u, i);
    }
    num = 0; DFS1(1);
    num = 0; DFS2(1, 1);
    Build(1, 1, num);
    Q = read();
    string opt;
    while (Q--) {
        std::cin >> opt;
        int tmp1 = tree[1].sum;
        if (opt == "install") {
            int x = read() + 1;
            Update(1,x,1);
            int tmp2 = tree[1].sum;
            printf("%d\n", abs(tmp1 - tmp2));
        }
        if (opt == "uninstall") {
            int x = read() + 1;
            Change(1,id[x],id[x]+size[x]-1,0);
            int tmp2 = tree[1].sum;
            printf("%d\n", abs(tmp1 - tmp2));
        }
    }
    return 0;
}

Luogu2590 [ZJOI2008]树的统计

比较简单的一道树剖,线段树部分更加简单,能单点修改区间查询即可。

Code

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 30000 + 5;

int n, Q, num, cnt;
int head[SIZE], son[SIZE], Size[SIZE], top[SIZE], depth[SIZE], fa[SIZE], id[SIZE], Rank[SIZE], w[SIZE];

struct node {
    int to, Next;
} edge[SIZE << 1];

struct Segment_tree {
    int sum, Max;
} tree[SIZE << 2];

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

inline void Addedge(int x, int y)
{
    edge[++num].to = y;
    edge[num].Next = head[x];
    head[x] = num;
}

inline void DFS1(int u)
{
    depth[u] = depth[fa[u]] + 1, Size[u] = 1;
    for (int i = head[u]; i; i = edge[i].Next) {
        int v = edge[i].to;
        if (v == fa[u]) continue;
        fa[v] = u;
        DFS1(v);
        Size[u] += Size[v];
        if (!son[u] || Size[son[u]] < Size[v]) son[u] = v;
    }
}

inline void DFS2(int u, int TOP)
{
    top[u] = TOP, id[u] = ++cnt, Rank[cnt] = u;
    if (!son[u]) return;
    DFS2(son[u], TOP);
    for (int i = head[u]; i; i = edge[i].Next) {
        int v = edge[i].to;
        if (v != son[u] && v != fa[u]) DFS2(v, v);
    }
}

inline void Pushup(int x)
{
    tree[x].sum = tree[x << 1].sum + tree[x << 1 | 1].sum;
    tree[x].Max = std::max(tree[x << 1].Max, tree[x << 1 | 1].Max);
}

inline void Build(int l, int r, int x)
{
    if (l == r) {
        tree[x].sum = tree[x].Max = w[Rank[l]];
        return;
    }
    int Mid = (l + r) >> 1;
    Build(l, Mid, x << 1); Build(Mid + 1, r, x << 1 | 1);
    Pushup(x);
}

inline void Change(int x, int p, int l, int r, int val)
{
    if (l == r) {
        tree[x].sum = tree[x].Max = val;
        return;
    }
    int Mid = (l + r) >> 1;
    if (p <= Mid) Change(x << 1, p, l, Mid, val);
    else Change(x << 1 | 1, p, Mid + 1, r, val);
    Pushup(x);
}

inline int Query_sum(int x, int L, int R, int l, int r)
{
    if (L <= l && r <= R) return tree[x].sum;
    int Mid = (l + r) >> 1, sum = 0;
    if (L <= Mid) sum += Query_sum(x << 1, L, R, l, Mid);
    if (R > Mid) sum += Query_sum(x << 1 | 1, L, R, Mid + 1, r);
    return sum;
}

inline int Query_max(int x, int L, int R, int l, int r)
{
    if (L <= l && r <= R) return tree[x].Max;
    int Mid = (l + r) >> 1, sum = -2e9;
    if (L <= Mid) sum = std::max(sum, Query_max(x << 1, L, R, l, Mid));
    if (R > Mid) sum = std::max(sum, Query_max(x << 1 | 1, L, R, Mid + 1, r));
    return sum;
}

inline int Get_max(int u, int v)
{
    int ans = -2e9;
    while (top[u] != top[v]) {
        if (depth[top[u]] < depth[top[v]]) std::swap(u, v);
        ans = std::max(ans, Query_max(1, id[top[u]], id[u], 1, n));
        u = fa[top[u]];
    }
    if (depth[u] > depth[v]) std::swap(u, v);
    ans = std::max(ans, Query_max(1, id[u], id[v], 1, n));
    return ans;
}

inline int Get_sum(int u, int v)
{
    int ans = 0;
    while (top[u] != top[v]) {
        if (depth[top[u]] < depth[top[v]]) std::swap(u, v);
        ans += Query_sum(1, id[top[u]], id[u], 1, n);
        u = fa[top[u]];
    }
    if (depth[u] > depth[v]) std::swap(u, v);
    ans += Query_sum(1, id[u], id[v], 1, n);
    return ans;
}

int main()
{
    // freopen("data.in", "r", stdin));
    int u, v, t;
    n = read();
    for (int i = 1; i < n; i++) {
        u = read(), v = read();
        Addedge(u, v); Addedge(v, u);
    }   
    for (int i = 1; i <= n; i++) w[i] = read();
    cnt = 0; DFS1(1);
    cnt = 0; DFS2(1, 1);
    Build(1, n, 1);
    Q = read();
    string opt;
    while (Q--) {
        std::cin >> opt;
        if (opt == "CHANGE") {
            u = read(), t = read();
            Change(1, id[u], 1, n, t);
        }
        if (opt == "QMAX") {
            u = read(), v = read();
            printf("%d\n", Get_max(u, v));
        }
        if (opt == "QSUM") {
            u = read(), v = read();
            printf("%d\n", Get_sum(u, v));
        }
    }
    return 0;
}

Luogu3178 [HAOI2015]树上操作

"您好这一题跟上一题有差别吗?"

"您好没有"

:joy:

其实是有的,线段树部分仍然只需单点修改区间查询即可。

这个修改是修改子树中所有点的点权,其他的修改也相应地变为增加而不是直接改变。

Code

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int SIZE = 100000 + 5;

int n, m, num, cnt;
int head[SIZE], a[SIZE], son[SIZE], Size[SIZE], fa[SIZE], depth[SIZE], id[SIZE], Rank[SIZE], top[SIZE];

struct node {
    int to, Next;
} edge[SIZE << 1];

struct Segment_tree {
    int l, r, sum, tag;
} tree[SIZE << 2];

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

inline void Addedge(int x, int y)
{
    edge[++num].to = y;
    edge[num].Next = head[x];
    head[x] = num;
}

inline void DFS1(int u)
{
    depth[u] = depth[fa[u]] + 1, Size[u] = 1;
    for (int i = head[u]; i; i = edge[i].Next) {
        int v = edge[i].to;
        if (v == fa[u]) continue;
        fa[v] = u;
        DFS1(v);
        Size[u] += Size[v];
        if (!son[u] || Size[son[u]] < Size[v]) son[u] = v;
    }
}

inline void DFS2(int u, int TOP)
{
    top[u] = TOP, id[u] = ++cnt, Rank[cnt] = u;
    if (!son[u]) return; 
    DFS2(son[u], TOP);
    for (int i = head[u]; i; i = edge[i].Next) {
        int v = edge[i].to;
        if (v != son[u] && v != fa[u]) DFS2(v, v);
    }
}

inline int pos(int x) { return tree[x].r - tree[x].l + 1; }

inline void Pushdown(int x)
{
    if (tree[x].tag) {
        tree[x << 1].sum += pos(x << 1) * tree[x].tag;
        tree[x << 1 | 1].sum += pos(x << 1 | 1) * tree[x].tag;
        tree[x << 1].tag += tree[x].tag, tree[x << 1 | 1].tag += tree[x].tag;
        tree[x].tag = 0;
    }
}

inline void Build(int x, int l, int r)
{
    tree[x].l = l, tree[x].r = r;
    if (l == r) {
        tree[x].sum = a[Rank[l]];
        return;
    }
    int Mid = (l + r) >> 1;
    Build(x << 1, l, Mid); Build(x << 1 | 1, Mid + 1, r);
    tree[x].sum = tree[x << 1].sum + tree[x << 1 | 1].sum;
}

inline void Change(int x, int l, int r, int val)
{
    if (l <= tree[x].l && tree[x].r <= r) {
        tree[x].sum += val * pos(x), tree[x].tag += val;
        return;
    }
    Pushdown(x);
    int Mid = (tree[x].l + tree[x].r) >> 1;
    if (l <= Mid) Change(x << 1, l, r, val);
    if (r > Mid) Change(x << 1 | 1, l, r, val);
    tree[x].sum = tree[x << 1].sum + tree[x << 1 | 1].sum;
}

inline int Query(int x, int l, int r)
{
    if (l <= tree[x].l && tree[x].r <= r) return tree[x].sum;
    Pushdown(x);
    int Mid = (tree[x].l + tree[x].r) >> 1, sum = 0;
    if (l <= Mid) sum += Query(x << 1, l, r);
    if (r > Mid) sum += Query(x << 1 | 1, l, r);
    return sum;
}

inline int Get_ans(int u, int v)
{
    int ans = 0;
    while (top[u] != top[v]) {
        if (depth[top[u]] < depth[top[v]]) std::swap(u, v);
        ans += Query(1, id[top[u]], id[u]);
        u = fa[top[u]];
    }
    if (depth[u] > depth[v]) std::swap(u, v);
    ans += Query(1, id[u], id[v]);
    return ans;
}

signed main()
{
    int u, v;
    n = read(), m = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    for (int i = 1; i < n; i++) {
        u = read(), v = read();
        Addedge(u, v);
        Addedge(v, u);
    }
    cnt = 0; DFS1(1);
    cnt = 0; DFS2(1, 1);
    cnt = 0; Build(1, 1, n);
    while (m--) {
        int opt = read();
        if (opt == 1) {
            int x = read(), val = read();
            Change(1, id[x], id[x], val);
        }
        if (opt == 2) {
            u = read(), v = read();
            Change(1, id[u], id[u] + Size[u] - 1, v);
        }
        if (opt == 3) {
            u = read();
            printf("%lld\n", Get_ans(1, u));
        }
    }
    return 0;
}

Luogu1505 [国家集训队]旅游

这个题是最傻逼的一个,操作贼多,代码超长

线段树维护单点修改,区间修改(乘),区间询问最大最小值,求和。

并且还是询问一条链的以上信息。

看代码好了。

Code

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 20000 + 5;

int n, Q, num, cnt;
int head[SIZE], w[SIZE], son[SIZE], Size[SIZE], depth[SIZE], fa[SIZE], id[SIZE], Rank[SIZE], top[SIZE];

struct node {
    int to, v, Next;
} edge[SIZE << 2];

struct Segment_tree {
    int l, r, tag, sum, Min, Max;
} tree[SIZE << 2];

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

inline void Addedge(int x, int y, int z)
{
    edge[++num].to = y;
    edge[num].v = z;
    edge[num].Next = head[x];
    head[x] = num;
}

inline void DFS1(int u)
{
    Size[u] = 1;
    for (int i = head[u]; i; i = edge[i].Next) {
        int v = edge[i].to;
        if (v == fa[u]) continue;
        fa[v] = u, w[v] = edge[i].v, depth[v] = depth[u] + 1;
        DFS1(v);
        Size[u] += Size[v];
        if (!son[u] || Size[son[u]] < Size[v]) son[u] = v;
    }
}

inline void DFS2(int u, int TOP)
{
    top[u] = TOP, id[u] = ++cnt, Rank[cnt] = u;
    if (son[u]) DFS2(son[u], TOP);
    for (int i = head[u]; i; i = edge[i].Next) {
        int v = edge[i].to;
        if (v != fa[u] && v != son[u]) DFS2(v, v);
    }
}

inline void Pushdown(int x)
{
    tree[x << 1].tag += tree[x].tag, tree[x << 1].tag %= 2;
    tree[x << 1 | 1].tag += tree[x]. tag, tree[x << 1 | 1].tag %= 2;
    tree[x << 1].sum *= -1, tree[x << 1 | 1].sum *= -1;
    std::swap(tree[x << 1].Max, tree[x << 1].Min);
    tree[x << 1].Max *= -1, tree[x << 1].Min *= -1;
    std::swap(tree[x << 1 | 1].Max, tree[x << 1 | 1].Min);
    tree[x << 1 | 1].Max *= -1, tree[x << 1 | 1].Min *= -1;
    tree[x].tag = 0;
}

inline void Pushup(int x) 
{
    tree[x].sum = tree[x << 1].sum + tree[x << 1 | 1].sum;
    tree[x].Max = std::max(tree[x << 1].Max, tree[x << 1 | 1].Max);
    tree[x].Min = std::min(tree[x << 1].Min, tree[x << 1 | 1].Min);
}

inline void Build(int x, int l, int r)
{
    tree[x].l = l, tree[x].r = r, tree[x].tag = 0;
    if (l == r) {
        tree[x].sum = tree[x].Max = tree[x].Min = w[Rank[l]];
        return;
    }
    int Mid = (l + r) >> 1;
    Build(x << 1, l, Mid); Build(x << 1 | 1, Mid + 1, r);
    Pushup(x);
}

inline void changeSingle(int x, int p, int val)
{
    if (tree[x].l == tree[x].r) {
        tree[x].sum = tree[x].Min = tree[x].Max = val;
        return;
    }
    if (tree[x].tag) Pushdown(x);
    int Mid = (tree[x].l + tree[x].r) >> 1;
    if (Mid >= p) changeSingle(x << 1, p, val);
    else changeSingle(x << 1 | 1, p, val);
    Pushup(x);
}

inline void changeInterval(int x, int l, int r)
{
    if (l <= tree[x].l && tree[x].r <= r) {
        tree[x].tag++; tree[x].tag %= 2; tree[x].sum *= -1;
        std::swap(tree[x].Max, tree[x].Min);
        tree[x].Max *= -1, tree[x].Min *= -1;
        return;
    }
    if (tree[x].tag) Pushdown(x);
    int Mid = (tree[x].l + tree[x].r) >> 1;
    if (Mid >= l) changeInterval(x << 1, l, r);
    if (Mid + 1 <= r) changeInterval(x << 1 | 1, l, r);
    Pushup(x);
}

inline int querySum(int x, int l, int r)
{
    if (l <= tree[x].l && tree[x].r <= r) return tree[x].sum;
    if (tree[x].tag) Pushdown(x);
    int Mid = (tree[x].l + tree[x].r) >> 1, sum = 0;
    if (l <= Mid) sum += querySum(x << 1, l, r);
    if (Mid + 1 <= r) sum += querySum(x << 1 | 1, l, r);
    Pushup(x);
    return sum;
}

inline int queryMin(int x, int l, int r)
{
    if (l <= tree[x].l && tree[x].r <= r) return tree[x].Min;
    if (tree[x].tag) Pushdown(x);
    int Mid = (tree[x].l + tree[x].r) >> 1, sum = 2e9;
    if (l <= Mid) sum = std::min(sum, queryMin(x << 1, l, r));
    if (Mid + 1 <= r) sum  = std::min(sum, queryMin(x << 1 | 1, l, r));
    Pushup(x);
    return sum;
}

inline int queryMax(int x, int l, int r)
{
    if (l <= tree[x].l && tree[x].r <= r) return tree[x].Max;
    if (tree[x].tag) Pushdown(x);
    int Mid = (tree[x].l + tree[x].r) >> 1, sum = -2e9;
    if (l <= Mid) sum = std::max(sum, queryMax(x << 1, l, r));
    if (Mid + 1 <= r) sum  = std::max(sum, queryMax(x << 1 | 1, l, r));
    Pushup(x);
    return sum;
}

inline int getSum(int u, int v)
{
    int ans = 0;
    while (top[u] != top[v]) {
        if (depth[top[u]] < depth[top[v]]) std::swap(u, v);
        ans += querySum(1, id[top[u]], id[u]);
        u = fa[top[u]];
    }
    if (u == v) return ans;
    if (id[u] > id[v]) std::swap(u, v);
    ans += querySum(1, id[u] + 1, id[v]);
    return ans;
}

inline int getMax(int u, int v)
{
    int ans = -2e9;
    while (top[u] != top[v]) {
        if (depth[top[u]] < depth[top[v]]) std::swap(u, v);
        ans = std::max(ans, queryMax(1, id[top[u]], id[u]));
        u = fa[top[u]];
    }
    if (u == v) return ans;
    if (id[u] > id[v]) std::swap(u, v);
    ans = std::max(ans, queryMax(1, id[u] + 1, id[v]));
    return ans;
}

inline int getMin(int u, int v)
{
    int ans = 2e9;
    while (top[u] != top[v]) {
        if (depth[top[u]] < depth[top[v]]) std::swap(u, v);
        ans = std::min(ans, queryMin(1, id[top[u]], id[u]));
        u = fa[top[u]];
    }
    if (u == v) return ans;
    if (id[u] > id[v]) std::swap(u, v);
    ans = std::min(ans, queryMin(1, id[u] + 1, id[v]));
    return ans;
}

inline void Update(int u, int v)
{
    while (top[u] != top[v]) {
        if (depth[top[u]] < depth[top[v]]) std::swap(u, v);
        changeInterval(1, id[top[u]], id[u]);
        u = fa[top[u]];
    }
    if (u == v) return;
    if (id[u] > id[v]) std::swap(u, v);
    changeInterval(1, id[u] + 1, id[v]);
}

int main()
{
    // freopen("data.in", "r", stdin);
    // freopen("data.out", "w", stdout);
    int u, v, d;
    n = read();
    for (int i = 1; i < n; i++) {
        u = read() + 1, v = read() + 1, d = read();
        Addedge(u, v, d); Addedge(v, u, d);
    }
    cnt = 0; DFS1(1);
    cnt = 0; DFS2(1, 1);
    cnt = 0; Build(1, 1, n);
    Q = read();
    string opt;
    while (Q--) {
        std::cin >> opt;
        if (opt == "C") {
            u = read() + 1, v = read();
            changeSingle(1, id[u], v);
        }   
        if (opt == "N") {
            u = read() + 1, v = read() + 1;
            Update(u, v);
        }
        if (opt == "SUM") {
            u = read() + 1, v = read() + 1;
            printf("%d\n", getSum(u, v));
        }
        if (opt == "MAX") {
            u = read() + 1, v = read() + 1;
            printf("%d\n", getMax(u, v));
        }
        if (opt == "MIN") {
            u = read() + 1, v = read() + 1;
            printf("%d\n", getMin(u, v));
        }
    }
    return 0;
}

Luogu4427 [BJOI2018]求和

这题不是很常规的树剖(就是没有那么多恶心的操作),该题不涉及修改。

观察 k 的范围很小,可以直接在树剖预处理的时候处理出每一个点的 k 次幂,询问倍增暴跳求和即可。

统计答案记得差分。

Code

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int SIZE = 300000 + 5;
const int Mod = 998244353;

int n, Q, num;
int head[SIZE], depth[SIZE], size[SIZE], son[SIZE], fa[SIZE], top[SIZE], sum[SIZE][55];

struct node {
    int to, Next;
} edge[SIZE << 1];

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

inline void Addedge(int x, int y)
{
    edge[++num].to = y;
    edge[num].Next = head[x];
    head[x] = num;
}

inline int Qpow(int x, int y)
{
    int ans = 1;
    while (y) {
        if (y & 1) ans = ans * x % Mod;
        x = x * x % Mod;
        y >>= 1;
    }
    return ans % Mod;
}

inline void DFS1(int u, int father)
{
    size[u] = 1;
    for (int i = 1; i <= 51; i++) sum[u][i] = (sum[father][i] + Qpow(depth[u], i)); // TEST1
    for (int i = head[u]; i; i = edge[i].Next) {
        int v = edge[i].to;
        if (v == fa[u]) continue;
        fa[v] = u, depth[v] = depth[u] + 1;
        DFS1(v, u);
        size[u] += size[v];
        if (size[son[u]] < size[v]) son[u] = v;
    }
}

inline void DFS2(int u, int TOP)
{
    top[u] = TOP;
    if (son[u]) DFS2(son[u], TOP);
    for (int i = head[u]; i; i = edge[i].Next) {
        int v = edge[i].to;
        if (v != fa[u] && v != son[u]) 
            DFS2(v, v);
    }
}

inline int LCA(int u, int v)
{
    while (top[u] != top[v]) {
        if (depth[top[u]] > depth[top[v]]) u = fa[top[u]];
        else v = fa[top[v]];
    }
    if (depth[u] < depth[v]) return u;
    return v;
}

signed main()
{
    int u, v, k;
    n = read();
    for (int i = 1; i < n; i++) {
        u = read(), v = read();
        Addedge(u, v); Addedge(v, u);
    }
    DFS1(1, 0); DFS2(1, 1);
    Q = read();
    while (Q--) {
        u = read(), v = read(), k = read();
        int lca = LCA(u, v);
        printf("%lld\n", (sum[u][k] + sum[v][k] - sum[lca][k] - sum[fa[lca]][k]) % Mod);
    }
    return 0;
}

SP3978 DISQUERY - Distance Query

我是绝对不会告诉你这是倍增LCA题的

其实可以用树剖做的,懒得写了,倍增也能过,码量少,何乐而不为?
跳的时候同时处理 Min[][], Max[][]两个数组就好了。

Code

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 100000 + 5;

int n, Q, num, t;
int head[SIZE], depth[SIZE], dis[SIZE], f[SIZE][21], Min[SIZE][21], Max[SIZE][21];

struct node {
    int to, v, Next;
} edge[SIZE << 1];

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

inline void Addedge(int x, int y, int z)
{
    edge[++num].to = y;
    edge[num].v = z;
    edge[num].Next = head[x];
    head[x] = num;
}

inline void DFS(int u, int fa)
{
    f[u][0] = fa;
    for (int i = head[u]; i; i = edge[i].Next) {
        int v = edge[i].to;
        if (v != fa) {
            Min[v][0] = Max[v][0] = edge[i].v;
            depth[v] = depth[u] + 1;
            DFS(v, u);
        }
    }
}

inline void init()
{
    for (int k = 1; k <= 20; k++)
        for (int i = 1; i <= n; i++) {
            if (f[f[i][k - 1]][k - 1] && f[i][k - 1]) {
                f[i][k] = f[f[i][k - 1]][k - 1];
                Min[i][k] = std::min(Min[i][k - 1], Min[f[i][k - 1]][k - 1]);
                Max[i][k] = std::max(Max[i][k - 1], Max[f[i][k - 1]][k - 1]);
            }
        }
}

inline void LCA(int u, int v)
{
    int ans_min = 2e9, ans_max = -2e9;
    if (depth[u] > depth[v]) std::swap(u, v);
    for (int i = 20; i >= 0; i--) {
        if (depth[u] <= depth[f[v][i]]) {
            ans_min = std::min(ans_min, Min[v][i]), ans_max = std::max(ans_max, Max[v][i]);
            v = f[v][i];
        }
    }
    if (u == v) {
        printf("%d %d\n", ans_min, ans_max);
        return;
    }
    for (int i = 20; i >= 0; i--) {
        if (f[u][i] != f[v][i]) {
            ans_min = std::min(ans_min, std::min(Min[u][i], Min[v][i])), ans_max = std::max(ans_max, std::max(Max[u][i], Max[v][i]));
            u = f[u][i], v = f[v][i];
        }
    }
    ans_min = std::min(ans_min, std::min(Min[u][0], Min[v][0]));
    ans_max = std::max(ans_max, std::max(Max[u][0], Max[v][0]));
    printf("%d %d\n", ans_min, ans_max);
}

int main()
{
    int u, v, d;
    n = read();
    for (int i = 1; i < n; i++) {
        u = read(), v = read(), d = read();
        Addedge(u, v, d);
        Addedge(v, u, d);
    }
    depth[1] = 1;
    DFS(1, 0);
    Min[1][0] = 2e9;
    init();
     Q = read();
     while (Q--) {
         u = read(), v = read();
         LCA(u, v);
     }
    return 0;
}

细心的观众可能意识到了到这里其实还只有七题

但是由于 【数据删除】【数据删除】 第八题暂时咕咕咕。

我还是绝对不会告诉你开始标题是树剖九题的


朴实沉毅