【拾题杂谈】LuoguP3384 【模板】重链剖分/树链剖分

题面：【模板】重链剖分/树链剖分

大秦为你打开题目传送门

题目描述

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

• 1 x y z，表示将树从 $x$ 到 $y$ 结点最短路径上所有节点的值都加上 $z$。

• 2 x y，表示求树从 $x$ 到 $y$ 结点最短路径上所有节点的值之和。

• 3 x z，表示将以 $x$ 为根节点的子树内所有节点值都加上 $z$。

• 4 x 表示求以 $x$ 为根节点的子树内所有节点值之和

输入格式

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

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

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

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

输出格式

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

样例 #1

样例输入 #1

5 5 2 24
7 3 7 8 0 
1 2
1 5
3 1
4 1
3 4 2
3 2 2
4 5
1 5 1 3
2 1 3

样例输出 #1

2
21

提示

【数据规模】

对于 $30\%$ 的数据： $1 \leq N \leq 10$，$1 \leq M \leq 10$；

对于 $70\%$ 的数据： $1 \leq N \leq {10}^3$，$1 \leq M \leq {10}^3$；

对于 $100\%$ 的数据： $1\le N \leq {10}^5$，$1\le M \leq {10}^5$，$1\le R\le N$，$1\le P \le 2^{30}$。所有输入的数均在 int 范围内。

【样例说明】

树的结构如下：

各个操作如下：

故输出应依次为 $2$ 和 $21$。

思路

模板题，出门右转 【算法介绍】树链剖分 | 祝馀宫 谢谢。

本题用到的性质：

1. 子树连号
2. 重链连号

没了。

代码

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

typedef long long ll;
// typedef __int128 int128;
typedef pair<int , int > pii;
typedef unsigned long long ull;

namespace FastIO 
{
    // char buf[1 << 20], *p1, *p2;
    // #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
    template<typename T> inline T read(T& x) {
        x = 0;
        int f = 1;
        char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
        return x;
    }
    template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
        read(x);
        read(x_...);
        return;
    }
    inline ll read() {
        ll x;
        read(x);
        return x;
    }
};
using namespace FastIO;

int P;

struct Node {
    // some basic viariables
    ll sum;
    Node() { sum = 0; }
    Node operator + (const Node& b) const {
        Node ans; ans.sum = (sum + b.sum) % P; return ans;
    }
};
template<const int N>
class SegTree {
private: 
    Node node[N];
    int lc[N], rc[N], cntn;
    ll lazy[N];
public :
    // clear function
    void clear(int rt) {
        if(!rt) return ;
        lazy[rt] = 0, node[rt] = Node();
        clear(lc[rt]);
        clear(rc[rt]);
        lc[rt] = rc[rt] = 0;
    }
    inline int newNode() {
        cntn++;
        lc[cntn] = rc[cntn] = lazy[cntn] = 0;
        return cntn;
    }
    // AddOperation    now   nowl   nowr  addval
    inline void Add(int rt, int l, int r, ll val) {
        (node[rt].sum += val * (r - l + 1) % P) %= P;
        (lazy[rt] += val) %= P;
    }
    // PushDownOperation    now   nowl   nowr
    inline void PushDown(int rt, int l, int r) {
        if(l == r || !lazy[rt]) return ;
        int mid = (l + r) >> 1;
        if(!lc[rt]) lc[rt] = newNode();
        Add(lc[rt], l, mid, lazy[rt]);
        if(!rc[rt]) rc[rt] = newNode();
        Add(rc[rt], mid + 1, r, lazy[rt]);
        lazy[rt] = 0;
    }
    // range Modify now   nowl   nowr   qizl   qizr   addval
    void Modify(int &rt, int l, int r, int L, int R, ll val) {
        if(!rt) rt = newNode();
        // cout << rt << ' ' << l << ' ' << r << endl;
        if(L <= l && r <= R) {
            Add(rt, l, r, val);
            return;
        }
        PushDown(rt, l, r);
        int mid = (l + r) >> 1;
        if(L <= mid) Modify(lc[rt], l, mid, L, R, val);
        if(R > mid) Modify(rc[rt], mid + 1, r, L, R, val);
        node[rt] = node[lc[rt]] + node[rc[rt]];
    }
    // range Query now   nowl   nowr   qizl   qizr
    Node Query(int &rt, int l, int r, int L, int R) {
        if(!rt) rt = newNode();
        // cout << rt << endl;
        if(L <= l && r <= R) return node[rt];
        PushDown(rt, l, r);
        int mid = (l + r) >> 1;
        Node res; 
        // set some basic value for res
        res.sum = 0;
        if(L <= mid) res = res + Query(lc[rt], l, mid, L, R);
        if(R > mid) res = res + Query(rc[rt], mid + 1, r, L, R);
        return res;
    }
};

template<int N, int M>
class Graph {
    private :
        struct Edge {
            int to, nt, wt;
            Edge() {}
            Edge(int to, int nt, int wt) : to(to), nt(nt), wt(wt) {}
        }e[M];
        int hd[N], cnte;
    public :
        inline void clear() { memset(hd, 0, sizeof(hd)), cnte = 0; }
        inline void AddEdge(int u, int v, int w = 0) {
            e[++cnte] = Edge(v, hd[u], w);
            hd[u] = cnte;
        }
        inline int head(int u) { return hd[u]; }
        inline int nt(int u) { return e[u].nt; }
        inline int to(int u) { return e[u].to; }
        inline int wt(int u) { return e[u].wt; }
};

const int MaxV = 1e5 + 10;
const int MaxE = 2e5 + 10;

int n, m, r;
int a[MaxV];
Graph< MaxV , MaxE >G;
SegTree< MaxV << 5 > Tree; int rt;

inline void Input() {
    read(n, m, r, P);
    for(int i = 1; i <= n; i++) {
        read(a[i]);
    }
    int u, v;
    for(int i = 1; i < n; i++) {
        read(u, v);
        G.AddEdge(u, v);
        G.AddEdge(v, u);
    }
}

int fa[MaxV], dep[MaxV];
int sz[MaxV], son[MaxV];
int top[MaxV];
int id[MaxV], rk[MaxV], cntd;

void Dfs(int u, int F) {
    fa[u] = F, dep[u] = dep[F] + 1, sz[u] = 1;
    for(int i = G.head(u); i; i = G.nt(i)) {
        int v = G.to(i);
        if(v == F) continue;
        Dfs(v, u);
        sz[u] += sz[v];
        if(sz[v] > sz[son[u]]) son[u] = v;
    }
    // cout << u << ' ' << son[u] << endl;
}

void Dfs2(int u, int t) {
    id[u] = ++cntd;
    rk[cntd] = u;
    top[u] = t;
    if(!son[u]) return ;
    Dfs2(son[u], t);
    for(int i = G.head(u); i; i = G.nt(i)) {
        int v = G.to(i);
        if(v != son[u] && v != fa[u]) Dfs2(v, v);
    }
}

inline void ModifyRange(int x, int y, int z) {
    z %= P;
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        Tree.Modify(rt, 1, n, id[top[x]], id[x], z);
        x = fa[top[x]];
    }
    if(id[x] > id[y]) swap(x, y);
    Tree.Modify(rt, 1, n, id[x], id[y], z);
}

inline void QueryRange(int x, int y) {
    int ans = 0;
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        (ans += Tree.Query(rt, 1, n, id[top[x]], id[x]).sum) %= P;
        x = fa[top[x]];
    }
    if(id[x] > id[y]) swap(x, y);
    (ans += Tree.Query(rt, 1, n, id[x], id[y]).sum) %= P;
    printf("%d\n", ans);
}

inline void ModifyTree(int x, int z) {
    Tree.Modify(rt, 1, n, id[x], id[x] + sz[x] - 1, z);
}

inline void QueryTree(int x) {
    printf("%d\n", Tree.Query(rt, 1, n, id[x], id[x] + sz[x] - 1).sum % P);
}

inline void Work() {
    Dfs(r, r); Dfs2(r, r);
    // cout << 1 << endl;
    for(int i = 1; i <= n; i++) {
        // cout << id[i] << endl;
        Tree.Modify(rt, 1, n, id[i], id[i], a[i]);
    }
    // cout << 2 << endl;
    int op, x, y, z;
    while(m--) {
        read(op);
        if(op == 1) {
            read(x, y, z);
            ModifyRange(x, y, z);
        }
        else if(op == 2) {
            read(x, y);
            QueryRange(x, y);
        }
        else if(op == 3) {
            read(x, z);
            ModifyTree(x, z);
        }
        else {
            read(x);
            QueryTree(x);
        }
    }
}

int main() {
    int T = 1;
    while(T--) {
        Input();
        Work();
    }
    return 0;
}