树链剖分

核心思想

通过给树上的每一个点重新编号，使得我们可以让树上的任意一条路径转化为 $O(\log n)$ 段连续的区间。

需要处理的问题：

• 将树从x到y结点最短路径上所有节点的值都加上z

• 求树从x到y结点最短路径上所有节点的值之和

• 将以x为根节点的子树内所有节点值都加上z

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

概念

• 重儿子：对于每一个非叶子节点，它的儿子中 以那个儿子为根的子树节点数最大的儿子 为该节点的重儿子
• 轻儿子：对于每一个非叶子节点，它的儿子中 非重儿子 的剩下所有儿子即为轻儿子
• 叶子节点没有重儿子也没有轻儿子
• 重边：一个父亲连接他的重儿子的边称为重边
• 轻边：剩下的即为轻边
• 重链：相邻重边连起来的 连接一条重儿子 的链叫重链
• 对于叶子节点，若其为轻儿子，则有一条以自己为起点的长度为1的链 每一条重链以轻儿子为起点

如何对树进行拆分

先用 $dfs1$ 找出轻重儿子等，然后用 $dfs$ 序遍历（ $dfs$ 序 指 优先遍历重儿子）。

Code

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

#define ll long long

using namespace std;

const int N = 100010;

struct Node
{
    int left, right;
    ll add; // add -> lazy tag
    ll dat; // the information which you need to protect;
}tree[4 * N + 5];

int n, m, root, p;
int weight[N],ver[N * 2], head[N], edge[2 * N], next_[N * 2], tot;
int deep[N], id[N], new_weight[N], cnt;
int son_size[N], top[N], fa[N], son[N]; //top -> the top node of each line fa -> the father node of each node
// son -> the heavy son of each node 


void add(int x, int y)
{
    ver[tot] = y, next_[tot] = head[x], head[x] = tot++;
}

void pushup(int u)
{
    tree[u].dat = tree[u << 1].dat + tree[u << 1 | 1].dat;
    tree[u].dat %= p;
}

void pushdown(int u)
{
    if (tree[u].add)
    {
        tree[u << 1].add += tree[u].add;
        tree[u << 1].add %= p;
        tree[u << 1].dat += tree[u].add * (tree[u << 1].right - tree[u << 1].left + 1);
        tree[u << 1].dat %= p;
        tree[u << 1 | 1].add += tree[u].add;
        tree[u << 1 | 1].add %= p;
        tree[u << 1 | 1].dat += tree[u].add * (tree[u << 1 | 1].right - tree[u << 1 | 1].left + 1);
        tree[u << 1 | 1].dat %= p;
        tree[u].add = 0;
    }
}

void build(int u, int l, int r)
{
	tree[u].left = l;
    tree[u].right = r;
    tree[u].add = 0;
    if (l == r) 
    {
        tree[u].dat = new_weight[r];
        return ;
    }
    
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}



void modify(int u, int l, int r, int k)
{
    if (tree[u].left >= l && tree[u].right <= r)
    {
        tree[u].add += k;
        tree[u].add %= p;
        tree[u].dat += k * (tree[u].right - tree[u].left + 1);
        tree[u].dat %= p;
        return ;
    }
    pushdown(u);
    int mid = tree[u].left + tree[u].right >> 1;
    if (l <= mid) modify(u << 1, l, r, k);
    if (r > mid) modify(u << 1 | 1, l, r, k);
    pushup(u);
}

ll ask (int u, int l, int r)
{
    if (tree[u].left >= l && tree[u].right <= r) return tree[u].dat;
    pushdown(u);
    int mid = tree[u].left + tree[u].right >> 1;
    ll res = 0;
    if (l <= mid) res += ask(u << 1, l, r), res %= p;
    if (r > mid) res += ask(u << 1 | 1, l, r), res %= p;
    return res;
}

void modify_path(int u, int v, int k)
{
    while(top[u] != top[v])
    {
        if (deep[top[u]] < deep[top[v]]) swap(u, v);
        modify(1, id[top[u]], id[u], k);
        u = fa[top[u]];
    }
    if (deep[u] < deep[v]) swap(u, v);
    modify(1, id[v], id[u], k);
}

ll ask_path(int u, int v)
{
    ll res = 0;
    while(top[u] != top[v])
    {
        if (deep[top[u]] < deep[top[v]]) swap(u, v);
        res += ask(1, id[top[u]], id[u]);
        res %= p;
        u = fa[top[u]];
    }
    if (deep[u] < deep[v]) swap(u, v);
    res += ask(1, id[v], id[u]);
    return res % p;
}

void modify_tree(int u, int k)
{
    modify(1, id[u], id[u] + son_size[u] - 1, k);
}

ll ask_tree(int u)
{
    return ask(1, id[u], id[u] + son_size[u] - 1);
}

void dfs1(int u, int father, int depth)
{
    deep[u] = depth, fa[u] = father, son_size[u] = 1;
    for (int i = head[u]; ~i; i = next_[i])
    {
        int j = ver[i];
        if (j == father) continue;
        dfs1(j, u, depth + 1);
        son_size[u] += son_size[j];
        if (son_size[son[u]] < son_size[j]) son[u] = j;
    }
}

void dfs2(int u, int t)
{
    id[u] = ++cnt, new_weight[cnt] = weight[u], top[u] = t;
    if (!son[u]) return ;
    dfs2(son[u], t);
    for (int i = head[u]; ~i ; i = next_[i])
    {
        int j = ver[i];
        if (j == fa[u] || j == son[u]) continue;
        dfs2(j, j);
    }
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &root, &p);
    for (int i = 1; i <= n; i++) scanf("%d", &weight[i]), weight[i] %= p;
    memset(head, -1, sizeof head);
    for (int i = 0; i < n - 1; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        add(b, a);
    }
    dfs1(root, -1, 1);
    dfs2(root, root);
    build(1, 1, cnt);
    while(m--)
    {
        int op, u, v, k;
        scanf("%d%d", &op, &u);
        if (op == 1)
        {
            scanf("%d%d", &v, &k);
            modify_path(u, v, k);
        }
        else if (op == 2)
        {
            scanf("%d", &v);
            printf("%lld\n", ask_path(u, v));
        }
        else if (op == 3)
        {
            scanf("%d", &k);
            modify_tree(u, k);
        }
        else 
        {
            printf("%lld\n", ask_tree(u));
        }
    }
    return 0;
}