树链剖分 学习笔记

树链剖分是一种思想，可以用来通过给树中每个点重新编号，从而让树中任意一条路径转化成 \(O(log n)\) 段连续区间（链）。树中任意一条路径均可以变成不超过 \(log n\) 段连续区间。从而把树的问题变成区间的问题（线段树维护）。

核心：
（1）将一棵树转化成一个序列。
（2）将树中路径转化成 \(O(log n)\) 段连续区间。

概念：
（1）重儿子 / 轻儿子：非叶节点，节点个数最多的一个子树的根节点叫做重儿子（多个最大值选一个即可），反之称为轻儿子。
（2）重边 / 轻边：对应重儿子 / 轻儿子，根节点与重儿子连的边叫重边，反之叫轻边。
（3）重链：对应重边，重边构成的链叫重链。

如何将整棵树变成一个序列？dfs 序，优先遍历重儿子（走重链）。

重要结论：

• 树中的任意一条路径均可拆分成 \(O(log n)\) 个重链，即 \(O(log n)\) 个连续区间。

code

int n, m, w[N], h[N], e[M], ne[M], idx, id[N], nw[N], cnt, dep[N], sz[N], top[N], fa[N], son[N];

struct Tree
{
    int l, r;
    LL add, sum;
}tr[N * 4];

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

void dfs1(int u, int father, int depth)
{
    dep[u] = depth, fa[u] = father, sz[u] = 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == father) continue;
        dfs1(j, u, depth + 1);
        sz[u] += sz[j];
        if (sz[son[u]] < sz[j]) son[u] = j;
    }
}

void dfs2(int u, int t)
{
    id[u] = ++ cnt, nw[cnt] = w[u], top[u] = t;
    if (!son[u]) return;
    dfs2(son[u], t);
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa[u] || j == son[u]) continue;
        dfs2(j, 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 += root.add, left.sum += root.add * (left.r - left.l + 1);
        right.add += root.add, right.sum += root.add * (right.r - right.l + 1);
        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 += k;
        tr[u].sum += k * (tr[u].r - tr[u].l + 1);
        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 += query(u << 1, l, r);
    if (r > mid) res += query(u << 1 | 1, l, r);
    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, id[top[u]], id[u], k);
        u = fa[top[u]];
    }
    if (dep[u] < dep[v]) swap(u, v);
    update(1, id[v], id[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 += query(1, id[top[u]], id[u]);
        u = fa[top[u]];
    }
    if (dep[u] < dep[v]) swap(u, v);
    res += query(1, id[v], id[u]);
    return res;
}

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

LL query_tree(int u){ return query(1, id[u], id[u] + sz[u] - 1);}

习题选做：
P1505 【国家集训队】 旅游
P2146 【NOI2015】 软件包管理器
P5773 【JSOI2016】 轻重路径
P8334 【ZJOI2022】 深搜
P2542 【AHOI2005】 航线规划
P2486 【SDOI2011】染色
P2590 【ZJOI2008】 树的统计
P3178 【HAOI2015】 树上操作
P3250 【HNOI2016】 网络
P3258 【JLOI2014】 松鼠的新家
P3313 【SDOI2014】旅行
P3703 【SDOI2017】 树点涂色
P3781 【SDOI2017】 切树游戏
P3833 【SHOI2012】 魔法树
P3976 【TJOI2015】 旅游
P4069 【SDOI2016】 游戏
P4092 【HEOI2016/TJOI2016】 树
P4175 【CTSC2008】 网络管理
P4211 【LNOI2014】 LCA
P4281 【AHOI2008】 紧急集合 / 聚会
P4332 【SHOI2014】 三叉神经树
P4338 【ZJOI2018】 历史
P4427 【BJOI2018】 求和
P4679 【ZJOI2011】 道馆之战