重链剖分⚓︎

重链剖分（ $\text{Heavy Light Decomposition}，\text{HLD}$ ）是一种将树划分为若干条链的技术，旨在将树上的路径查询和更新问题转化为链上的区间查询和更新问题，从而利用线段树或树状数组等数据结构高效地处理这些操作。

重链剖分的基本思想是将树中的每个节点划分为"重边"和"轻边"。对于每个节点，选择其子节点中子树大小最大的边作为重边，其余的边作为轻边。这样，从根节点到任意叶节点的路径上，重边的数量不会超过 $\log n$ ，其中 $n$ 是树的节点数。

通过重链剖分，可以将树上的路径查询和更新操作转化为若干条链上的区间查询和更新操作，从而利用线段树或树状数组等数据结构高效地处理这些操作。具体来说，重链剖分的步骤包括：

计算子树大小：通过深度优先搜索（ $\text{DFS}$ ）计算每个节点的子树大小
划分重边和轻边：对于每个节点，选择子树大小最大的边作为重边，其余的边作为轻边
编号：对每条链使用（ $\text{DFS}$ ）编号得到 $\text{DFS}$ 序，保证同一条链上的节点在 $\text{DFS}$ 序中是连续的
构建线段树或树状数组：根据链的编号和位置，构建线段树或树状数组，以支持链上的区间查询和更新操作
路径查询和更新：将树上的路径查询和更新操作转化为若干条链上的区间查询和更新操作，并利用线段树或树状数组高效地处理这些操作

$\text{DFN}$

$\text{DFN}$ （ $\text{Depth-First Numbering}$ ）是指在对树进行深度优先搜索（ $\text{DFS}$ ）遍历时，为每个节点分配一个唯一的编号，编号的顺序与节点被访问的顺序一致。通过 $\text{DFN}$ ，可以将树上的节点映射到一个线性数组中，从而方便地进行区间查询和更新操作。

对于路径查询和更新操作，可以将路径上的节点划分为若干条链，并在每条链上使用 $\text{DFN}$ 进行区间操作。

子树节点的 $\text{DFN}$ 是连续的。假设节点 $u$ 的 $\text{DFN}$ 编号为 $dfn[u]$ ，其子树的大小为 $size[u]$ ，那么以 $u$ 为根的子树 $\text{DFN}$ 的范围可以表示为 $[dfn[u], dfn[u] + size[u] - 1]$ 。子树操作对应该区间。

如果是边的性质，则下放到子节点，然后：

对于路径操作，最后一步排除 $\text{LCA}$ 节点，即最后查询的是 $[dfn[u] + 1, dfn[v]]$ 。
对于子树操作，排除根节点，即查询的是 $[dfn[u] + 1, dfn[u] + size[u] - 1]$ 。

【模板】重链剖分/树链剖分

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

将路径 $u$ 到 $v$ 上的所有节点的数值加上 $k$ 。
查询路径 $u$ 到 $v$ 上所有节点的数值之和。
将以 $u$ 为根的子树上所有节点的数值加上 $k$ 。
查询以 $u$ 为根的子树上所有节点的数值之和。

C++

#include <cstdint>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

struct segment_tree {
  vector<int64_t> sum;      // 区间和
  vector<int64_t> tag_add;  // 区间加法懒标记

  int64_t p;  // 模数

  explicit segment_tree(int64_t n, int64_t p) : sum(n * 4), tag_add(n * 4), p(p) {}

  void push_up(int64_t i) { sum[i] = sum[2 * i] + sum[2 * i + 1]; }

  // 构建线段树
  void build(int64_t i, int64_t left, int64_t right, const vector<int64_t> &nums,
             const vector<int64_t> &rank) {
    if (left == right) {  // 叶子节点，进行初始化, 将dfn映射回节点编号
      sum[i] = nums[rank[left]] % p;
      return;
    }
    int64_t mid = left + ((right - left) / 2);
    build(2 * i, left, mid, nums, rank);
    build(2 * i + 1, mid + 1, right, nums, rank);
    push_up(i);
  }

  void lazy_add(int64_t i, int64_t val, int64_t count) {
    sum[i]     = (sum[i] + count * val) % p;
    tag_add[i] = (tag_add[i] + val) % p;
  }

  // 向下传递懒标记
  void push_down(int64_t i, int64_t left_count, int64_t right_count) {
    if (tag_add[i] != 0) {  // 将加法标记传递给子节点
      lazy_add(2 * i, tag_add[i], left_count);
      lazy_add(2 * i + 1, tag_add[i], right_count);
      tag_add[i] = 0;  // 清空根节点加法标记
    }
  }

  // 区间加法: range_add(x, y, val, 1, 1, n) 将区间 [x,y] 的值加上 val
  void range_add(int64_t ql, int64_t qr, int64_t val, int64_t i, int64_t l, int64_t r) {
    if (ql <= l && r <= qr) {  // 区间覆盖, 直接更新
      lazy_add(i, val, r - l + 1);
      return;
    }
    int64_t mid = l + ((r - l) / 2);
    push_down(i, mid - l + 1, r - mid);
    if (ql <= mid) { range_add(ql, qr, val, 2 * i, l, mid); }
    if (qr > mid) { range_add(ql, qr, val, 2 * i + 1, mid + 1, r); }
    push_up(i);
  }

  // 区间求和: range_sum(x, y, 1, 1, n) 查询区间 [x,y] 的和
  int64_t range_sum(int64_t ql, int64_t qr, int64_t i, int64_t l, int64_t r) {
    if (ql <= l && r <= qr) { return sum[i]; }  // 区间覆盖，直接返回
    int64_t mid = l + ((r - l) / 2);
    push_down(i, mid - l + 1, r - mid);
    // 汇总结果
    int64_t res = 0;
    if (ql <= mid) { res = (res + range_sum(ql, qr, 2 * i, l, mid)) % p; }
    if (qr > mid) { res = (res + range_sum(ql, qr, 2 * i + 1, mid + 1, r)) % p; }
    return res;
  }
};

int main() {
  int n, m, r, p;
  cin >> n >> m >> r >> p;
  vector<int64_t> nums(n + 1);
  for (int i = 1; i <= n; ++i) { cin >> nums[i]; }
  vector<vector<int64_t>> tree(n + 1);
  for (int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;
    tree[u].push_back(v);
    tree[v].push_back(u);
  }

  // 父节点, 深度, 子树大小, 重儿子
  vector<int64_t> parent(n + 1), depth(n + 1), size(n + 1), heavy_son(n + 1, -1);
  auto dfs = [&](auto &self, int64_t u, int64_t from) -> void {
    parent[u]        = from;
    size[u]          = 1;
    int64_t max_size = 0;
    for (int64_t v : tree[u]) {
      if (v != from) {
        depth[v] = depth[u] + 1;
        self(self, v, u);
        size[u] += size[v];
        if (size[v] > max_size) {
          max_size     = size[v];
          heavy_son[u] = v;
        }
      }
    }
  };
  dfs(dfs, r, -1);  // 计算父节点, 深度, 子树大小, 重儿子

  // 链顶, dfs序, dfs反序(dfn为i的节点编号)
  vector<int64_t> top(n + 1), dfn(n + 1), rank(n + 1);
  int64_t timer  = 0;
  auto decompose = [&](auto &self, int64_t u, int64_t t) -> void {
    top[u]      = t;
    dfn[u]      = ++timer;
    rank[timer] = u;
    if (heavy_son[u] != -1) { self(self, heavy_son[u], t); }  // (1)!
    for (int64_t v : tree[u]) {  // 处理轻儿子, 轻儿子各自成链，链顶为自己
      if (v != parent[u] && v != heavy_son[u]) { self(self, v, v); }
    }
  };
  decompose(decompose, r, r);  // 重链剖分, 根节点为r, 链顶为自己

  segment_tree seg(n, p);
  seg.build(1, 1, n, nums, rank);  // 根据dfn构建线段树, 注意rank将dfn映射回节点编号

  auto path_sum = [&](int64_t u, int64_t v) {
    int64_t res = 0;
    while (top[u] != top[v]) {  // (2)!
      if (depth[top[u]] < depth[top[v]]) { swap(u, v); }
      res = (res + seg.range_sum(dfn[top[u]], dfn[u], 1, 1, n)) % p;
      u   = parent[top[u]];
    }
    if (depth[u] > depth[v]) { swap(u, v); }  // (3)!
    res = (res + seg.range_sum(dfn[u], dfn[v], 1, 1, n)) % p;
    return res;
  };

  auto path_add = [&](int64_t u, int64_t v, int64_t val) {
    while (top[u] != top[v]) {
      if (depth[top[u]] < depth[top[v]]) { swap(u, v); }
      seg.range_add(dfn[top[u]], dfn[u], val, 1, 1, n);
      u = parent[top[u]];
    }
    if (depth[u] > depth[v]) { swap(u, v); }
    seg.range_add(dfn[u], dfn[v], val, 1, 1, n);
  };

  for (int i = 0; i < m; ++i) {
    int op;
    cin >> op;
    if (op == 1) {
      int x, y, z;
      cin >> x >> y >> z;
      path_add(x, y, z);
    } else if (op == 2) {
      int x, y;
      cin >> x >> y;
      cout << path_sum(x, y) << "\n";
    } else if (op == 3) {
      int x, z;
      cin >> x >> z;
      seg.range_add(dfn[x], dfn[x] + size[x] - 1, z, 1, 1, n);  // (4)!
    } else {
      int x;
      cin >> x;
      cout << seg.range_sum(dfn[x], dfn[x] + size[x] - 1, 1, 1, n) << "\n";
    }
  }
  return 0;
}

优先处理重儿子, 保证重链上的节点在 $\text{DFS}$ 序中是连续的, 重链上所有节点的链顶为 $top$
当 $u$ 和 $v$ 不在同一条链上时，提升较深节点所在链的链顶节点的父节点，直到 $u$ 和 $v$ 在同一条链上。
提升过程中记录区间和或进行区间更新。
当 $u$ 和 $v$ 在同一条链上时，直接计算区间和或进行区间更新。注意 $u$ 和 $v$ 的相对位置。
以 $u$ 为根的子树在 $\text{DFS}$ 序中的范围为 $[dfn[u], dfn[u] + size[u] - 1]$ ，直接对该区间进行查询或更新。

【模板】最近公共祖先（LCA）

已知一棵包含 $N$ 个结点的树（连通且无环），需要处理 $M$ 次最近公共祖先（ $\text{LCA}$ ）查询。

其他解法见最近公共祖先（LCA）。

C++

#include <cstdint>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n, m, s;
  cin >> n >> m >> s;
  vector<vector<int>> tree(n + 1);
  for (int i = 0; i < n - 1; ++i) {
    int x, y;
    cin >> x >> y;
    tree[x].push_back(y);
    tree[y].push_back(x);
  }

  // 父节点, 深度, 子树大小, 重儿子
  vector<int64_t> parent(n + 1), depth(n + 1), size(n + 1), heavy_son(n + 1, -1);
  auto dfs = [&](auto &self, int64_t u, int64_t from) -> void {
    parent[u]        = from;
    size[u]          = 1;
    int64_t max_size = 0;
    for (int64_t v : tree[u]) {
      if (v != from) {
        depth[v] = depth[u] + 1;
        self(self, v, u);
        size[u] += size[v];
        if (size[v] > max_size) {
          max_size     = size[v];
          heavy_son[u] = v;
        }
      }
    }
  };
  dfs(dfs, s, -1);  // 计算父节点, 深度, 子树大小, 重儿子

  // 链顶, dfs序, dfn反序(dfn为i的节点编号)
  vector<int64_t> top(n + 1), dfn(n + 1), rank(n + 1);
  int64_t timer  = 0;
  auto decompose = [&](auto &self, int64_t u, int64_t t) -> void {
    top[u]      = t;
    dfn[u]      = ++timer;
    rank[timer] = u;
    if (heavy_son[u] != -1) { self(self, heavy_son[u], t); }
    for (int64_t v : tree[u]) {
      if (v != parent[u] && v != heavy_son[u]) { self(self, v, v); }
    }
  };
  decompose(decompose, s, s);  // 重链剖分

  auto get_lca = [&](int64_t u, int64_t v) -> int64_t {
    while (top[u] != top[v]) {
      if (depth[top[u]] < depth[top[v]]) { swap(u, v); }
      u = parent[top[u]];
    }
    return depth[u] < depth[v] ? u : v;
  };

  for (int i = 0; i < m; ++i) {
    int x, y;
    cin >> x >> y;
    cout << get_lca(x, y) << "\n";
  }

  return 0;
}

树上最小公倍数追踪

给定一棵有 $N$ 个节点的树和 $M$ 个查询，每个节点为黑色或白色，操作包括两种：

将节点 $x$ 的颜色在黑色和白色之间切换。
查询节点 $x$ 和节点 $y$ 之间路径上所有黑色节点值的最小公倍数。

需要网站会员提交

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>
using namespace std;

const int64_t MOD = 1e9 + 7;

struct segment_tree {
  vector<int64_t> lcm;  // 区间最小公倍数

  explicit segment_tree(int64_t n) : lcm(n * 4) {}

  void push_up(int64_t i) { lcm[i] = std::lcm(lcm[2 * i], lcm[2 * i + 1]); }

  // 构建线段树
  void build(int64_t i, int64_t left, int64_t right, const vector<int64_t> &nums,
             const vector<int64_t> &rank, const vector<int64_t> &colors) {
    if (left == right) {  // 叶子节点，进行初始化, 将dfn映射回节点编号
      int64_t index = rank[left];
      lcm[i]        = colors[index] == 1 ? nums[index] : 1;
      return;
    }
    int64_t mid = left + ((right - left) / 2);
    build(2 * i, left, mid, nums, rank, colors);
    build(2 * i + 1, mid + 1, right, nums, rank, colors);
    push_up(i);
  }

  // 单点修改: point_set(x, val, 1, 1, n) 将下标 x 的值修改为 val
  void point_set(int64_t index, int64_t val, int64_t i, int64_t left, int64_t right) {
    if (left == index && right == index) {  // 到叶子，直接修改数组中的值
      lcm[i] = val;
      return;
    }
    int64_t mid = left + ((right - left) / 2);
    if (index <= mid) {
      point_set(index, val, 2 * i, left, mid);
    } else {
      point_set(index, val, 2 * i + 1, mid + 1, right);
    }
    push_up(i);
  }

  int64_t range_lcm(int64_t ql, int64_t qr, int64_t i, int64_t l, int64_t r) {
    if (ql <= l && r <= qr) { return lcm[i]; }
    int64_t mid = l + ((r - l) / 2);
    int64_t res = 1;
    if (ql <= mid) { res = std::lcm(res, range_lcm(ql, qr, 2 * i, l, mid)); }
    if (qr > mid) { res = std::lcm(res, range_lcm(ql, qr, 2 * i + 1, mid + 1, r)); }
    return res;
  }
};

int main() {
  int64_t n, q;
  cin >> n >> q;

  vector<int64_t> nums(n + 1);
  for (int64_t i = 1; i <= n; ++i) { cin >> nums[i]; }

  vector<int64_t> colors(n + 1);  // 0表示白色, 1表示黑色
  for (int64_t i = 1; i <= n; ++i) {
    char color;
    cin >> color;
    colors[i] = (color == 'B') ? 1 : 0;
  }

  vector<vector<int64_t>> tree(n + 1);
  for (int64_t i = 1; i < n; ++i) {
    int64_t u;
    int64_t v;
    cin >> u >> v;
    tree[u].push_back(v);
    tree[v].push_back(u);
  }
  // 父节点, 深度, 子树大小, 重儿子
  vector<int64_t> parent(n + 1), depth(n + 1), size(n + 1), heavy_son(n + 1, -1);
  auto dfs = [&](auto &self, int64_t u, int64_t from) -> void {
    parent[u]        = from;
    size[u]          = 1;
    int64_t max_size = 0;
    for (int64_t v : tree[u]) {
      if (v != from) {
        depth[v] = depth[u] + 1;
        self(self, v, u);
        size[u] += size[v];
        if (size[v] > max_size) {
          max_size     = size[v];
          heavy_son[u] = v;
        }
      }
    }
  };

  dfs(dfs, 1, -1);  // 计算父节点, 深度, 子树大小, 重儿子

  // 链顶, dfs序, dfn反序(dfn为i的节点编号)
  vector<int64_t> top(n + 1), dfn(n + 1), rank(n + 1);
  int64_t timer  = 0;
  auto decompose = [&](auto &self, int64_t u, int64_t t) -> void {
    top[u]      = t;
    dfn[u]      = ++timer;
    rank[timer] = u;
    if (heavy_son[u] != -1) { self(self, heavy_son[u], t); }
    for (int64_t v : tree[u]) {
      if (v != parent[u] && v != heavy_son[u]) { self(self, v, v); }
    }
  };
  decompose(decompose, 1, 1);  // 重链剖分, 根节点为1, 链顶为自己

  segment_tree seg(n);
  seg.build(1, 1, n, nums, rank, colors);

  auto query_path = [&](int64_t u, int64_t v) {
    int64_t res = 1;
    while (top[u] != top[v]) {
      if (depth[top[u]] < depth[top[v]]) { swap(u, v); }
      res = std::lcm(res, seg.range_lcm(dfn[top[u]], dfn[u], 1, 1, n));
      u   = parent[top[u]];
    }
    if (depth[u] > depth[v]) { swap(u, v); }
    res = std::lcm(res, seg.range_lcm(dfn[u], dfn[v], 1, 1, n));
    return res;
  };

  for (int64_t i = 0; i < q; ++i) {
    int64_t op;
    int64_t x;
    cin >> op >> x;
    if (op == 1) {  // 修改颜色, 相当于单点修改
      colors[x]   ^= 1;
      int64_t val  = colors[x] == 1 ? nums[x] : 1;
      seg.point_set(dfn[x], val, 1, 1, n);
    } else if (op == 2) {
      // 只对结果取模！！！
      cout << query_path(1, x) % MOD << '\n';
    }
  }

  return 0;
}

Grass Planting G

给定一棵有 $n$ 个节点的树，以及 $m$ 个操作，每个操作要么在 $u$ 和 $v$ 之间的边权加 $1$ ，要么查询 $u$ 和 $v$ 之间的边权和。初始时，所有边权均为 $0$ 。

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using PII  = pair<int, int>;
using TIII = tuple<int, int, int>;

struct segment_tree {
  vector<int64_t> sum;      // 区间和
  vector<int64_t> tag_add;  // 区间加法懒标记

  explicit segment_tree(int64_t n) : sum(n * 4), tag_add(n * 4) {}

  void push_up(int64_t i) { sum[i] = sum[2 * i] + sum[2 * i + 1]; }

  void lazy_add(int64_t i, int64_t val, int64_t count) {
    sum[i]     += count * val;
    tag_add[i] += val;
  }

  // 向下传递懒标记
  void push_down(int64_t i, int64_t left_count, int64_t right_count) {
    if (tag_add[i] != 0) {  // 将加法标记传递给子节点
      lazy_add(2 * i, tag_add[i], left_count);
      lazy_add(2 * i + 1, tag_add[i], right_count);
      tag_add[i] = 0;  // 清空根节点加法标记
    }
  }

  // 区间加法: range_add(x, y, val, 1, 1, n) 将区间 [x,y] 的值加上 val
  void range_add(int64_t ql, int64_t qr, int64_t val, int64_t i, int64_t l, int64_t r) {
    if (ql <= l && r <= qr) {  // 区间覆盖, 直接更新
      lazy_add(i, val, r - l + 1);
      return;
    }
    int64_t mid = l + ((r - l) / 2);
    push_down(i, mid - l + 1, r - mid);
    if (ql <= mid) { range_add(ql, qr, val, 2 * i, l, mid); }
    if (qr > mid) { range_add(ql, qr, val, 2 * i + 1, mid + 1, r); }
    push_up(i);
  }

  // 区间求和: range_sum(x, y, 1, 1, n) 查询区间 [x,y] 的和
  int64_t range_sum(int64_t ql, int64_t qr, int64_t i, int64_t l, int64_t r) {
    if (ql <= l && r <= qr) { return sum[i]; }  // 区间覆盖，直接返回
    int64_t mid = l + ((r - l) / 2);
    push_down(i, mid - l + 1, r - mid);
    // 汇总结果
    int64_t res = 0;
    if (ql <= mid) { res += range_sum(ql, qr, 2 * i, l, mid); }
    if (qr > mid) { res += range_sum(ql, qr, 2 * i + 1, mid + 1, r); }
    return res;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n, m;
  cin >> n >> m;

  vector<vector<int>> tree(n + 1);
  for (int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;
    tree[u].push_back(v);
    tree[v].push_back(u);
  }
  // 重链剖分准备
  int r = 1;  // 以1号节点为根节点
  // 父节点, 深度, 子树大小, 重儿子
  vector<int64_t> parent(n + 1), depth(n + 1), size(n + 1), heavy_son(n + 1, -1);
  auto dfs = [&](auto &self, int64_t u, int64_t from) -> void {
    parent[u]        = from;
    size[u]          = 1;
    int64_t max_size = 0;
    for (int64_t v : tree[u]) {
      if (v != from) {
        depth[v] = depth[u] + 1;
        self(self, v, u);
        size[u] += size[v];
        if (size[v] > max_size) {
          max_size     = size[v];
          heavy_son[u] = v;
        }
      }
    }
  };
  dfs(dfs, r, -1);  // 计算父节点, 深度, 子树大小, 重儿子

  // 链顶, dfs序, dfs反序(dfn为i的节点编号)
  vector<int64_t> top(n + 1), dfn(n + 1), rank(n + 1);
  int64_t timer  = 0;
  auto decompose = [&](auto &self, int64_t u, int64_t t) -> void {
    top[u]      = t;
    dfn[u]      = ++timer;
    rank[timer] = u;
    if (heavy_son[u] != -1) { self(self, heavy_son[u], t); }
    for (int64_t v : tree[u]) {  // 处理轻儿子, 轻儿子各自成链，链顶为自己
      if (v != parent[u] && v != heavy_son[u]) { self(self, v, v); }
    }
  };
  decompose(decompose, r, r);  // 重链剖分, 根节点为r, 链顶为自己
  // 构建线段树, 一开始都是关键边, 所以点权都为1
  segment_tree seg(n);
  // 查询u-v路径上的边权和
  auto path_sum = [&](int64_t u, int64_t v) {
    int64_t res = 0;
    while (top[u] != top[v]) {
      if (depth[top[u]] < depth[top[v]]) { swap(u, v); }
      res = (res + seg.range_sum(dfn[top[u]], dfn[u], 1, 1, n));
      u   = parent[top[u]];
    }
    if (depth[u] > depth[v]) { swap(u, v); }
    res = (res + seg.range_sum(dfn[u] + 1, dfn[v], 1, 1, n));
    return res;
  };
  // 将u-v路径上的边权加上val
  auto path_add = [&](int64_t u, int64_t v, int64_t val) {
    while (top[u] != top[v]) {
      if (depth[top[u]] < depth[top[v]]) { swap(u, v); }
      seg.range_add(dfn[top[u]], dfn[u], val, 1, 1, n);
      u = parent[top[u]];
    }
    if (depth[u] > depth[v]) { swap(u, v); }
    seg.range_add(dfn[u] + 1, dfn[v], val, 1, 1, n);
  };

  for (int i = 0; i < m; ++i) {
    char op;
    int u, v;
    cin >> op >> u >> v;
    if (op == 'P') {
      path_add(u, v, 1);
    } else {
      int64_t ans = path_sum(u, v);
      cout << ans << "\n";
    }
  }

  return 0;
}

重链剖分⚓︎

评论