学习笔记 - 树链剖分-轻重链剖分

树链剖分，是强行增加码量至 100+ 行的东西将一棵树拆分为若干条链，套用数据结构，以便于维护路径与子树信息的一种转换。

例题 P3384 【模板】轻重链剖分/树链剖分

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

• 1 x y z，表示将树从 $x$ 到 $y$ 结点最短路径上所有节点的值都加上 $z$。
• 2 x y，表示求树从 $x$ 到 $y$ 结点最短路径上所有节点的值之和。
• 3 x z，表示将以 $x$ 为根节点的子树内所有节点值都加上 $z$。
• 4 x 表示求以 $x$ 为根节点的子树内所有节点值之和。

实现

我们先考虑前两问。

如果这是在一个序列上，那么这就是线段树/树状数组模板题。

可惜不是。

那可不可以把它摊成一个区间再处理？

它毕竟是树，这做不到。

如果多个区间呢？能不能把一条路径拆成多个区间，也就是……链？

定义

• 重儿子：对于树上一个非叶子结点，它的儿子中所在子树最大的儿子即为其重儿子。
• 轻儿子：对于树上一个非叶子结点，它的儿子中不是重儿子的都是轻儿子。
• 重边：对于树上一个非叶子结点，它连向重儿子的边为重边。
• 轻边：对于树上一个非叶子结点，它连向轻儿子的边为轻边。
• 重链：由重边连接而成的链为重链。

例如：

如果这样子定义，是不是就可以保证全树被剖分为若干条重链了呢？

我们来确定几个性质。

性质分析

1. 每个点在且仅在一条重链上

对于一个重儿子，它自然是父亲传下来的重边的接续；对于一个轻儿子/根，它所在的链头就是自己。

因为一个非叶子结点只有一个重儿子，一条重链不可能分叉。

2. 每条链从上往下深度递增，以叶子结点结束

这个也很好理解，毕竟重链是父传子的，直到传不下去为止。

3. 从上往下遍历，每经过一条轻边，余下的子树大小至少减少一半

因为这个儿子有个兄弟，兄弟的子树不比自己小。显然，这样跳也就至少能减少一半。

换言之，在一棵大小为 $n$ 的树上，对于一条从上往下深度依次递增的路径，其至多经过 $O(\log n)$ 条重链。

4. 对于树的 DFS 序列，如果向下拓展时先走重儿子，则每条重链的映射（即 $dfn$）是连续的。每颗子树的映射也是连续的

预处理

在树链剖分中，我们要维护 $7$ 个数组（虽然许多时候只要 $6$ 个）：

• $fa_x$：每个节点的父亲。
• $son_x$：每个节点的重儿子。
• $depth_x$：每个节点的深度。
• $siz_x$：每个节点子树的大小。
• $anc_x$：每个节点所在重链的链头。
• $dfn_x$：记录每个点的映射。
• $rdfn_x$：记录每个映射对应的点（事实上许多时候不需要维护）。

我们分为两次。第一次处理前四个很容易处理的数组。第二次处理后三个。其实现只需要用基本的 dfs 即可。

回答：最近公共祖先

既然轻重链剖分的优势就是只要跳 $O(\log n)$ 次重链，我们就考虑两边分别向上跳重链。

那么我们就只有两个问题：每次由谁跳？跳到啥时候算完？

第二个问题比较好处理：如果两个点在同一重链上，其中深度低的必然就是最近公共祖先。

对于每次由谁跳，我们想想判断的依据。因为每次都是直接跳到节点所在链头之上，所以起决定作用的应该是两节点所在链头的深度。

显然，如果先跳链头低的，一定不会超过最近公共祖先。否则，如果先跳链头高的，可能就会超高了。

回答：路径修改/查询

我们知道一条重链上的点，映射是连续的。所以我们只需要套一个 LCA 的求法，用数据结构维护映射后的数组，每次修改/查询就是多个区间的修改/查询。

回答：子树修改/查询

我们还知道，在 DFS 序里，同一子树的映射也是连续的（即 $[dfn_u, dfn_u + siz_u]$）。所以我们甚至不用跳，直接一次区间修改/查询即可。

数据结构选用

我们的数据结构要支持区间修改/区间查询和，而且最好和每次询问的访问数 $O(\log n)$ 契合。显然，线段树是不二之选。当然，树状数组可能也可以。

代码

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

constexpr int MXV = 100005;
int val[MXV];
int DVS;
int root, V, opts;

int to[MXV << 1], nxt[MXV << 1], head[MXV], egsz;
void addedge(int a, int b) {
  to[egsz] = b;
  nxt[egsz] = head[a];
  head[a] = egsz++;
}

int siz[MXV], depth[MXV], fa[MXV], son[MXV];
void init1(int x, int f, int h) {
  siz[x] = 1;
  depth[x] = h;
  fa[x] = f;
  son[x] = -1;
  for (int i(head[x]); ~i; i = nxt[i]) {
    if (to[i] != f) {
      init1(to[i], x, h + 1);
      siz[x] += siz[to[i]];
      if (!~son[x] || siz[to[i]] > siz[son[x]]) son[x] = to[i];
    }
  }
}

int anc[MXV], ptoi[MXV], itop[MXV], dfn;
void init2(int x, int a) {
  anc[x] = a;
  ptoi[x] = dfn, itop[dfn++] = x;
  if (~son[x]) {
    init2(son[x], a);
    for (int i(head[x]); ~i; i = nxt[i])
      if (to[i] != fa[x] && to[i] != son[x]) init2(to[i], to[i]);
  }
}

int sum[MXV << 2], tag[MXV << 2];
void init3(int cur, int l, int r) {
  if (r - l == 1) {
    sum[cur] = val[itop[l]] % DVS;
    return;
  }
  int mid((l + r) >> 1);
  init3((cur << 1) + 1, l, mid);
  init3((cur + 1) << 1, mid, r);
  sum[cur] = (sum[(cur << 1) + 1] + sum[(cur + 1) << 1]) % DVS;
}

inline void pushdown(int p, int l, int r) {
  int ls((p << 1) + 1), rs((p + 1) << 1), mid((r + l) >> 1);
  tag[ls] = (tag[ls] + tag[p]) % DVS;
  sum[ls] = (sum[ls] + (mid - l) % DVS * tag[p] % DVS) % DVS;
  tag[rs] = (tag[rs] + tag[p]) % DVS;
  sum[rs] = (sum[rs] + (r - mid) % DVS * tag[p] % DVS) % DVS;
  tag[p] = 0;
}

inline void pushup(int p) {
  sum[p] = (sum[(p << 1) + 1] + sum[(p + 1) << 1]) % DVS;
}

void add(int cur, int l, int r, int curl, int curr, int k) {
  if (curr <= l || curl >= r) return;
  if (curl >= l && curr <= r) {
    tag[cur] = (tag[cur] + k) % DVS;
    sum[cur] = (sum[cur] + (curr - curl) % DVS * k % DVS) % DVS;
    return;
  }
  pushdown(cur, curl, curr);
  add((cur << 1) + 1, l, r, curl, (curl + curr) >> 1, k);
  add((cur + 1) << 1, l, r, (curl + curr) >> 1, curr, k);
  pushup(cur);
}

int ask(int cur, int l, int r, int curl, int curr) {
  if (curr <= l || curl >= r) return 0;
  if (curl >= l && curr <= r) return sum[cur];
  pushdown(cur, curl, curr);
  return (ask((cur << 1) + 1, l, r, curl, (curl + curr) >> 1) +
          ask((cur + 1) << 1, l, r, (curl + curr) >> 1, curr)) %
         DVS;
}

int read() {
  int x(0);
  char c(getchar());
  while (c < '0' || c > '9') c = getchar();
  while (c >= '0' && c <= '9')
    x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
  return x;
}

void write(int x) {
  if (x >= 10) write(x / 10);
  putchar((x % 10) | 48);
}

int main() {
  V = read(), opts = read(), root = read() - 1, DVS = read();
  fill(head, head + V, -1);
  for (int i(0); i != V; ++i) cin >> val[i];
  for (int i(1), a, b; i != V; ++i) {
    a = read() - 1, b = read() - 1;
    addedge(a, b), addedge(b, a);
  }
  init1(root, -1, 0);
  init2(root, root);
  init3(0, 0, V);
  for (int opt, x, y, z; opts--;) {
    opt = read(), x = read() - 1;
    switch (opt) {
      case 1: {
        y = read() - 1;
        z = read() % DVS;
        while (anc[x] != anc[y]) {
          if (depth[anc[x]] < depth[anc[y]]) swap(x, y);
          add(0, ptoi[anc[x]], ptoi[x] + 1, 0, V, z);
          x = fa[anc[x]];
        }
        if (depth[x] < depth[y]) swap(x, y);
        add(0, ptoi[y], ptoi[x] + 1, 0, V, z);
        break;
      }
      case 2: {
        y = read() - 1;
        int sum(0);
        while (anc[x] != anc[y]) {
          if (depth[anc[x]] < depth[anc[y]]) swap(x, y);
          sum = (sum + ask(0, ptoi[anc[x]], ptoi[x] + 1, 0, V)) % DVS;
          x = fa[anc[x]];
        }
        if (depth[x] < depth[y]) swap(x, y);
        write((sum + ask(0, ptoi[y], ptoi[x] + 1, 0, V)) % DVS), putchar('\n');
        break;
      }
      case 3: {
        z = read() % DVS;
        add(0, ptoi[x], ptoi[x] + siz[x], 0, V, z);
        break;
      }
      case 4: {
        write(ask(0, ptoi[x], ptoi[x] + siz[x], 0, V)), putchar('\n');
        break;
      }
    }
  }
  return 0;
}

练习

P2590 [ZJOI2008]树的统计

P2486 [SDOI2011]染色

P7735 [NOI2021] 轻重边