『题解』洛谷P3384 【模板】树链剖分

This article was last modified days ago. The content of this post may be outdated!

Portal

Portal1: Luogu

Description

如题，已知一棵包含$N$个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：

操作$1$：格式： 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上$z$；

操作$2$：格式： 2 x y 表示求树从x到y结点最短路径上所有节点的值之和；

操作$3$：格式： 3 x z 表示将以x为根节点的子树内所有节点值都加上$z$；

操作$4$：格式： 4 x 表示求以x为根节点的子树内所有节点值之和。

Input

第一行包含$4$个正整数$N$、$M$、$R$、$P$，分别表示树的结点个数、操作个数、根节点序号和取模数（即所有的输出结果均对此取模）。

接下来一行包含$N$个非负整数，分别依次表示各个节点上初始的数值。

接下来$N - 1$行每行包含两个整数$x$、$y$，表示点$x$和点$y$之间连有一条边（保证无环且连通）

接下来$M$行每行包含若干个正整数，每行表示一个操作，格式如下：

操作$1$： 1 x y z

操作$2$： 2 x y

操作$3$： 3 x z

操作$4$： 4 x

Output

输出包含若干行，分别依次表示每个操作$2$或操作$4$所得的结果（对$P$取模）。

Sample Input

Sample Output

2
21

Solution

模板树链剖分题。

一些概念：

重儿子：在每一个非叶子结点的儿子中，以那个儿子结点为根的子树的结点数最多的儿子为该结点的重儿子；
轻儿子：在非叶子，非重儿子结点；
重边：一个父亲结点连结它的重儿子的边；
轻边：非重边；
重链：相邻重边连起来的，连接一条重儿子结点的链叫重链。

dfs1的功能：

求出每结点的深度；
求出每个结点的父亲节点；
求出每个非叶子结点的子树的大小；
求出每个非叶子结点的重儿子的编号。

dfs2的功能：

处理每条链；
标记每个结点的新编号；
求出每个结点所在链的顶；
把结点的初始值更新到新编号里。

Code

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;

const int MAXN = 2000005;
struct EDGE {
    int u, v, nxt;
} edge[MAXN];
struct node {
    int l, r, w, size, f;
} tree[MAXN];
int n, m, root, mod, cnt, num = 1, a[MAXN], b[MAXN], tot[MAXN], son[MAXN], top[MAXN], idx[MAXN], dep[MAXN], head[MAXN], father[MAXN];
inline void addedge(int u, int v) {
    edge[num].u = u; edge[num].v = v; edge[num].nxt = head[u]; head[u] = num++;
}
//dep[i]表示i结点的深度
//father[i]表示i结点的父亲结点
//son[]表示重儿子的编号
inline int dfs1(int now, int f, int deep) {
    dep[now] = deep;
    father[now] = f;
    tot[now] = 1;
    int Maxson = -1;
    for (int i = head[now]; ~i; i = edge[i].nxt) {
        if (edge[i].v == f) continue;
        tot[now] += dfs1(edge[i].v, now, deep + 1);
        if (tot[edge[i].v] > Maxson) {
            Maxson = tot[edge[i].v];
            son[now] = edge[i].v;
        }
    }
    return tot[now];
}
inline void dfs2(int now, int topf) {
    idx[now] = ++cnt;
    a[cnt] = b[now];
    top[now] = topf;
    if (!son[now]) return ;
    dfs2(son[now], topf);
    for (int i = head[now]; ~i; i = edge[i].nxt)
        if (!idx[edge[i].v]) dfs2(edge[i].v, edge[i].v);
}
inline void pushup(int root) {
    tree[root].w = (tree[root << 1].w + tree[root << 1 | 1].w + mod) % mod;
}
inline void build(int root, int l, int r) {
    tree[root].l = l; tree[root].r = r; tree[root].size = r - l + 1;
    if (l == r) {
        tree[root].w = a[l];
        return ;
    }
    int mid = l + r >> 1;
    build(root << 1, l, mid);
    build(root << 1 | 1, mid + 1, r);
    pushup(root);
}
inline void pushdown(int root) {
    if (!tree[root].f) return ;
    tree[root << 1].w = (tree[root << 1].w + tree[root << 1].size * tree[root].f) % mod;
    tree[root << 1 | 1].w = (tree[root << 1 | 1].w + tree[root << 1 | 1].size * tree[root].f) % mod;
    tree[root << 1].f = (tree[root << 1].f + tree[root].f) % mod;
    tree[root << 1 | 1].f = (tree[root << 1 | 1].f + tree[root].f) % mod;
    tree[root].f = 0;
}
inline void update_add(int root, int ansl, int ansr, int val) {
    if (ansl <= tree[root].l && tree[root].r <= ansr) {
        tree[root].w += tree[root].size * val;
        tree[root].f += val;
        return ;
    }
    pushdown(root);
    int mid = tree[root].l + tree[root].r >> 1;
    if (ansl <= mid) update_add(root << 1, ansl, ansr, val);
    if (ansr > mid) update_add(root << 1 | 1, ansl, ansr, val);
    pushup(root);
}
//线段树操作
inline void tree_add(int x, int y, int val) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        update_add(1, idx[top[x]], idx[x], val);
        x = father[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    update_add(1, idx[x], idx[y], val);
}
inline int query_sum(int root, int ansl, int ansr) {
    int ret = 0;
    if (ansl <= tree[root].l && tree[root].r <= ansr) return tree[root].w;
    pushdown(root);
    int mid = tree[root].l + tree[root].r >> 1;
    if (ansl <= mid) ret = (ret + query_sum(root << 1, ansl, ansr)) % mod;
    if (ansr > mid) ret = (ret + query_sum(root << 1 | 1, ansl, ansr)) % mod;
    return ret;
}
inline void tree_sum(int x, int y) {
    int ret = 0;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        ret = (ret + query_sum(1, idx[top[x]], idx[x])) % mod;
        x = father[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    ret = (ret + query_sum(1, idx[x], idx[y])) % mod;
    printf("%d\n", ret);
}
int main() {
    memset(head, -1, sizeof(head));
    scanf("%d%d%d%d", &n, &m, &root, &mod);
    for (int i = 1; i <= n; i++)
        scanf("%d", &b[i]);
    for (int i = 1; i < n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        addedge(x, y);
        addedge(y, x);
    }
    dfs1(root, 0, 1);
    dfs2(root, root);
    build(1, 1, n);
    while (m--) {
        int opt, x, y, val;
        scanf("%d", &opt);
        if (opt == 1) {
            scanf("%d%d%d", &x, &y, &val);
            val %= mod;
            tree_add(x, y, val);
        } else
        if (opt == 2) {
            scanf("%d%d", &x, &y);
            tree_sum(x, y);
        } else
        if (opt == 3) {
            scanf("%d%d", &x, &val);
            update_add(1, idx[x], idx[x] + tot[x] - 1, val % mod);
        } else {
            scanf("%d", &x);
            printf("%d\n", query_sum(1, idx[x], idx[x] + tot[x] - 1));
        }
    }
    return 0;
}

Article License: CC BY-NC-ND 4.0
Article Author: XiaoHuang

题解

题解洛谷 C++ 模板树链剖分