树链剖分

树链剖分是指将一棵树形结构划分成若干条“链”

常见的剖分方式有重链剖分，长链剖分 … 等

它是将 树上的路径或者一棵子树，转化为区间问题 的一种“思想”

简单理解就是把一棵树转换成一个序列

重链剖分的步骤

1. 先计算出每个节点的子树的节点总数s[i]与每个节点的深度dep[i], 和父节点fa[i]

son[i]表示当前节点i的重儿子是谁

void dfs1(int u, int p, int depth)
{
    s[u] = 1;

    dep[u] = depth;
    fa[u] = p;

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];

        if (j != p)
        {
            dfs1(j, u, depth + 1);

            s[u] += s[j];

            if (s[son[u]] < s[j]) son[u] = j;
        }
    }
}

若当前节点为u并且它有两个儿子

其中左儿子为l, 右儿子为r

若s[l] > s[r], 则l为重儿子

否则r为轻儿子（根节点是特别的重儿子）

也就是u的的儿子中s[i]最大的就是重儿子

2. 对于每个轻儿子，以其为起点开启一条新的链， 一直向重儿子拓展

那么，整棵树将被划分为若干条链, 其中链头都是轻儿子, 脸上其他节点都是重儿子

重链剖分不唯一因为可能有两个“等价”的重儿子

一旦确定重儿子，这棵树的重链剖分就唯一了

3. 再次dfs给每个节点标记dfn序(时间戳), 并记录每个dfn序对于的节点

dfs途中优先去重儿子

轻儿子维护top[i] = i

重儿子维护top[i] = top[fa[i]];

void dfs2(int u) // 维护每条链的dfs序
{
    dfn[u] = ++timestamp;
    id[timestamp] = u;
    // 记录时间戳为timestamp的点为u, 线段树是以时间戳建树

    if (son[u]) // 有重儿子
    {
        top[son[u]] = top[u];
        // son[u]所在链头继承父节点u的链头

        dfs2(son[u]); // 优先去重链
    }

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];

        if (!top[j]) // 轻儿子
        {
            top[j] = j;
            // 轻儿子开启一条链， 链头是本身

            dfs2(j);
        }
    }
}

特别注意！！！top[root] = root;

重链剖分的性质

1. 重儿子不一定是唯一的但是确定每一个点的重儿子以后， 重链剖分是唯一的;

2. 一条重链总是从轻儿子开始的，再往下走都是重儿子;

3. 一条重链的dfn序是连续的区间;

4. 一颗子树的dfn序总是连续的区间;

5. 树上每个节点x到其链头top[x]的dfn序总是连续的;

6. 树上任意两个点x, y的路径可以由若干调重链的子点拼接而成, 也就是说x到y可以划分为若干段连续的dfn区间

7. 树上任意点x到任意点y, 链的切换之多logN次

重链剖分的应用

1. 重连剖分求lca

int lca(int a, int b)
{
    while (top[a] != top[b]) // a和b不在同一条链上
    {
        if (dep[top[a]] > dep[top[b]]) // 换成链头深度大的
            a = fa[top[a]];
        else
            b = fa[top[b]];
    }

    if (dep[a] > dep[b]) return b;

    return a;
}

2. 将树上路径转化为区间问题结合线段树树状数组，分块，莫队，双指针 … 等

一般与线段树结合

模板题 P3384

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

typedef long long ll;

const int N = 1e5 + 10, M = 2e5 + 10;
ll w[N], nw[N];
int h[N], e[M], ne[M], idx;
int dfn[N], timestamp;
int dep[N], s[N];
int top[N];
int fa[N], son[N];
ll n, m, root, mod;

struct Segment
{
    int l, r;
    ll add, sum;
} tr[N << 2];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs1(int u, int p, int depth)
{
    s[u] = 1;

    dep[u] = depth;
    fa[u] = p;

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];

        if (j != p)
        {
            dfs1(j, u, depth + 1);

            s[u] += s[j];

            if (s[son[u]] < s[j]) son[u] = j;
        }
    }
}

void dfs2(int u)
{
    dfn[u] = ++timestamp;
    nw[timestamp] = w[u];

    if (son[u])
    {
        top[son[u]] = top[u];

        dfs2(son[u]);
    }

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];

        if (!top[j])
        {
            top[j] = j;

            dfs2(j);
        }
    }
}

void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void pushdown(int u)
{
    auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];

    if (root.add)
    {
        left.add = (left.add + root.add) % mod;
        left.sum = (left.sum + root.add * (left.r - left.l + 1) % mod) % mod;

        right.add = (right.add + root.add) % mod;
        right.sum = (right.sum + root.add * (right.r - right.l + 1) % mod) % mod;
        root.add = 0;
    }
}

void build(int u, int l, int r)
{
    tr[u] = {l, r, 0, nw[r]};

    if (l == r) return;

    int mid = l + r >> 1;

    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);

    pushup(u);
}

void update(int u, int l, int r, int k)
{
    if (l <= tr[u].l && r >= tr[u].r)
    {
        tr[u].add = (tr[u].add + k) % mod;
        tr[u].sum = (tr[u].sum + k * (tr[u].r - tr[u].l + 1) % mod) % mod;
        return;
    }

    pushdown(u);

    int mid = tr[u].l + tr[u].r >> 1;

    if (l <= mid) update(u << 1, l, r, k);
    if (r > mid) update(u << 1 | 1, l, r, k);

    pushup(u);
}

ll query(int u, int l, int r)
{
    if (l <= tr[u].l && r >= tr[u].r) return tr[u].sum;

    pushdown(u);

    int mid = tr[u].l + tr[u].r >> 1;

    ll res = 0;
    if (l <= mid)
        res = (res + query(u << 1, l, r)) % mod;

    if (r > mid)
        res = (res + query(u << 1 | 1, l, r)) % mod;

    return res;
}

void update_path(int u, int v, int k)
{
    while (top[u] != top[v])
    {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);

        update(1, dfn[top[u]], dfn[u], k);

        u = fa[top[u]];
    }

    if (dep[u] < dep[v]) swap(u, v);

    update(1, dfn[v], dfn[u], k);
}

ll query_path(int u, int v)
{
    ll res = 0;
    while (top[u] != top[v])
    {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);

        res = (res + query(1, dfn[top[u]], dfn[u])) % mod;

        u = fa[top[u]];
    }

    if (dep[u] < dep[v]) swap(u, v);

    res = (res + query(1, dfn[v], dfn[u])) % mod;

    return res;
}

void update_tree(int u, int k)
{
    update(1, dfn[u], dfn[u] + s[u] - 1, k);
}

ll query_tree(int u)
{
    return query(1, dfn[u], dfn[u] + s[u] - 1);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> root >> mod;

    for (int i = 1; i <= n; i++)
    {
        cin >> w[i];

        w[i] %= mod;
    }

    memset(h, -1, sizeof h);

    int a, b;
    for (int i = 1; i < n; i++)
    {
        cin >> a >> b;

        add(a, b);
        add(b, a);
    }

    dfs1(root, 0, 1);

    top[root] = root;

    dfs2(root);

    build(1, 1, n);

    int t, u, v, k;
    while (m--)
    {
        cin >> t >> u;

        if (t == 1)
        {
            cin >> v >> k;

            update_path(u, v, k % mod);
        }
        else if (t == 2)
        {
            cin >> v;

            cout << query_path(u, v) << '\n';
        }
        else if (t == 3)
        {
            cin >> k;

            update_tree(u, k);
        }
        else cout << query_tree(u) << '\n';
    }


    return 0;
}