Skip to content

Heavy-Light Decomposition

Introduction

Heavy-light decomposition (HLD) is used to partition a tree into several chains, in order to maintain information on tree paths.

Specifically, the entire tree is decomposed into several chains, which are combined into a linear structure, and then other data structures are used to maintain the information.

Tree decomposition (tree partitioning / chain decomposition) comes in various forms, such as heavy-light decomposition, long-chain decomposition, and the decomposition used for Link/cut Tree (sometimes called "preferred path decomposition"). In most cases (unless specified otherwise), "tree decomposition" refers to "heavy-light decomposition".

Heavy-light decomposition can partition any path on the tree into at most \(O(\log n)\) continuous chains, where the depths of nodes on each chain are distinct (i.e., each chain is a bottom-up path, and the LCA of all nodes on the chain is one endpoint of the chain).

Heavy-light decomposition also ensures that the DFS order of nodes on each resulting chain is continuous, making it convenient to use data structures that maintain sequences (such as segment trees) to handle information on tree paths. For example:

  1. Modify the values of all nodes on the path between two nodes on the tree.
  2. Query the sum / extremum / other information (which can be maintained by data structures on sequences and easily merged) of node weights on the path between two nodes on the tree.

Besides cooperating with data structures to maintain path information, tree decomposition can also be used to find LCA in \(O(\log n)\) (with a small constant). In some problems, its properties can be flexibly utilized.

Heavy-Light Decomposition

We give some definitions:

Define heavy child as the child with the largest subtree size. If there are multiple children with the largest subtree size, choose one arbitrarily. If there is no child, then there is no heavy child.

Define light child as all remaining children.

The edge from this node to its heavy child is a heavy edge.

Edges to other light children are light edges.

Several heavy edges connected end-to-end form a heavy chain.

Treat isolated nodes as heavy chains as well, so the entire tree is partitioned into several heavy chains.

As shown in the figure:

HLD

Implementation

The implementation of tree decomposition involves two DFS processes. Pseudocode is as follows:

The first DFS records each node's parent (\(\textit{father}\)), depth (\(\textit{depth}\)), subtree size (\(\textit{size}\)), and heavy child (\(\textit{hson}\)).

\[ \begin{array}{l} \text{TREE-BUILD }(u,\textit{dep}) \\ \begin{array}{ll} 1 & u.\textit{hson}\gets 0 \\ 2 & u.\textit{hson}.\textit{size}\gets 0 \\ 3 & u.\textit{depth}\gets \textit{dep} \\ 4 & u.\textit{size}\gets 1 \\ 5 & \textbf{for }\text{each son }v\text{ of }u \\ 6 & \qquad u.\textit{size}\gets u.\textit{size} + \text{TREE-BUILD }(v,\textit{dep}+1) \\ 7 & \qquad v.\textit{father}\gets u \\ 8 & \qquad \textbf{if }v.\textit{size}> u.\textit{hson}.\textit{size} \\ 9 & \qquad \qquad u.\textit{hson}\gets v \\ 10 & \textbf{return } u.\textit{size} \end{array} \end{array} \]

The second DFS records the top of the chain where the node resides (\(\textit{top}\), which should be initialized to the node itself), the DFS order when traversing with heavy edges first (\(\textit{top}\)), and the node index corresponding to the DFS order (\(\textit{rank}\)).

\[ \begin{array}{l} \text{TREE-DECOMPOSITION }(u,\textit{top}) \\ \begin{array}{ll} 1 & u.\textit{top}\gets \textit{top} \\ 2 & \textit{tot}\gets \textit{tot}+1\\ 3 & u.\textit{dfn}\gets \textit{tot} \\ 4 & \textit{rank}(\textit{tot})\gets u \\ 5 & \textbf{if }u.\textit{hson}\text{ is not }0 \\ 6 & \qquad \text{TREE-DECOMPOSITION }(u.\textit{hson},\textit{top}) \\ 7 & \qquad \textbf{for }\text{each son }v\text{ of }u \\ 8 & \qquad \qquad \textbf{if }v\text{ is not }u.\textit{hson} \\ 9 & \qquad \qquad \qquad \text{TREE-DECOMPOSITION }(v,v) \end{array} \end{array} \]

The code implementation is given below.

We first give some definitions:

  • \(\operatorname{fa}(x)\) denotes the parent of node \(x\) in the tree.
  • \(\operatorname{dep}(x)\) denotes the depth of node \(x\) in the tree.
  • \(\operatorname{siz}(x)\) denotes the number of nodes in the subtree of node \(x\).
  • \(\operatorname{son}(x)\) denotes the heavy child of node \(x\).
  • \(\operatorname{top}(x)\) denotes the top node (with minimum depth) of the heavy chain containing node \(x\).
  • \(\operatorname{dfn}(x)\) denotes the DFS order of node \(x\), which is also its index in the segment tree.
  • \(\operatorname{rnk}(x)\) denotes the node index corresponding to the DFS order, satisfying \(\operatorname{rnk}(\operatorname{dfn}(x))=x\).

We perform two DFS passes to precompute these values. The first DFS computes \(\operatorname{fa}(x)\), \(\operatorname{dep}(x)\), \(\operatorname{siz}(x)\), \(\operatorname{son}(x)\). The second DFS computes \(\operatorname{top}(x)\), \(\operatorname{dfn}(x)\), \(\operatorname{rnk}(x)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
void dfs1(int u, int f) {
  fa[u] = f, dep[u] = dep[f] + 1, siz[u] = 1;
  for (auto v : G[u]) {
    if (v == f) continue;
    dfs1(v, u);
    siz[u] += siz[v];
    if (siz[v] > siz[son[u]]) son[u] = v;
  }
}

void dfs2(int u, int ftop) {
  top[u] = ftop, dfn[u] = ++idx, rnk[idx] = u;
  if (son[u]) dfs2(son[u], ftop);
  for (auto v : G[u])
    if (v != son[u] && v != fa[u]) dfs2(v, v);
}

Properties of Heavy-Light Decomposition

Every node in the tree belongs to exactly one heavy chain.

The starting node of a heavy chain is not necessarily a heavy child (because heavy edges are defined for every node).

All heavy chains completely partition the entire tree.

During decomposition, heavy edges are traversed first, so in the final DFS order of the tree, the DFS order within each heavy chain is continuous. The sequence sorted by DFN is the chain after decomposition.

The DFS order within a subtree is continuous.

We can observe that when we go down a light edge, the size of the subtree is at least halved.

Therefore, for any path on the tree, splitting it from the LCA going down both sides, each side traverses at most \(O(\log n)\) light edges. Thus, any path on the tree can be split into at most \(O(\log n)\) heavy chains.

How to reasonably challenge tree decomposition

Generally, the \(O(\log n)\) constant of tree decomposition is small and hard to challenge. To challenge it, one must construct a binary tree with low depth.

So we can consider a compromise.

We construct a binary tree with \(\sqrt{n}\) nodes. For each edge from a node to its child, we replace it with a chain of length \(\sqrt{n}\).

This way, we can make the average number of heavy-light switches for random queries reach \(\frac{\log n}{2}\), while the depth is \(O(\sqrt{n} \log n)\).

Adding some random leaves might seem to challenge tree decomposition. However, due to the small constant of tree decomposition, it might still not be enough.

Common Applications

Path Maintenance

Using tree decomposition to compute the sum of weights on the path between two nodes on the tree, pseudocode is as follows:

\[ \begin{array}{l} \text{TREE-PATH-SUM }(u,v) \\ \begin{array}{ll} 1 & \textit{tot}\gets 0 \\ 2 & \textbf{while }u.\textit{top}\text{ is not }v.\textit{top} \\ 3 & \qquad \textbf{if }u.\textit{top}.\textit{depth}< v.\textit{top}.\textit{depth} \\ 4 & \qquad \qquad \text{SWAP}(u, v) \\ 5 & \qquad \textit{tot}\gets \textit{tot} + \text{sum of values between }u\text{ and }u.\textit{top} \\ 6 & \qquad u\gets u.\textit{top}.\textit{father} \\ 7 & \textit{tot}\gets \textit{tot} + \text{sum of values between }u\text{ and }v \\ 8 & \textbf{return } \textit{tot} \end{array} \end{array} \]

The DFS order on a chain is continuous, so segment trees or Fenwick trees can be used for maintenance.

Each time, choose the chain with greater depth to jump up until both points are on the same chain.

The same jumping-chain structure applies to maintaining and querying other information on paths.

Subtree Maintenance

Sometimes, we need to maintain information on subtrees, such as increasing the weights of all nodes in the subtree rooted at \(x\) by \(v\).

During DFS, the DFS order of nodes in a subtree is continuous.

Each node records bottom to denote the end node of the continuous interval of its subtree.

This transforms subtree information into a continuous interval.

Finding Lowest Common Ancestor

Continuously jump up heavy chains. When jumping onto the same heavy chain, the node with smaller depth is the LCA.

When jumping up heavy chains, always jump the one whose chain top has greater depth first.

Reference code:

1
2
3
4
5
6
7
8
9
int lca(int u, int v) {
  while (top[u] != top[v]) {
    if (dep[top[u]] > dep[top[v]])
      u = fa[top[u]];
    else
      v = fa[top[v]];
  }
  return dep[u] > dep[v] ? v : u;
}

Root Change Operation

Consider a new type of problem: besides the basic operations supported by tree decomposition, a root change operation is added.

Since tree decomposition maintains static information and does not support dynamic modification, and it is impossible to recompute information after each root change due to high complexity, we need to fully utilize previously obtained information to handle root changes.

For path modification and query operations, since the simple path between two nodes on a tree is unique, it does not change, and can be handled in the normal way.

For subtree modification and query operations, the general idea is to map the subtree after root change to the original subtree. This requires classifying the relative positions of the root of the operation subtree, the root of the tree after root change, and the root of the original tree. Specific details are described in the example below.

Examples

This section demonstrates how to apply heavy-light decomposition through examples. First is a template problem.

「ZJOI2008」Tree Statistics

Given a static tree with \(n\) nodes, each node has a weight. Perform \(q\) operations of three types:

  1. Modify the weight of a single node;
  2. Query the maximum weight on the path from \(u\) to \(v\);
  3. Query the sum of weights on the path from \(u\) to \(v\).

Guarantee \(1\le n\le 30000\), \(0\le q\le 200000\).

Solution

According to the problem description and the properties mentioned earlier, the segment tree needs to support three operations:

  1. Single point modification;
  2. Interval query for maximum;
  3. Interval query for sum.

Single point modification is easy.

Since the DFS order of a subtree is continuous (whether tree decomposition is used or not), modifying a node's subtree only requires modifying this continuous DFS order interval.

The problem is how to modify/query the path between two nodes.

Consider how we find LCA using binary lifting. First, we bring both nodes to the same height, then jump both nodes up together. For tree decomposition, we can use a similar idea.

During the upward jump, if the current node is on a heavy chain, jump to the top of the heavy chain; if the current node is not on a heavy chain, jump up one node. Repeat until the two nodes coincide. Update/query interval information along the way.

For each query, at most \(O(\log n)\) heavy chains are traversed, and each heavy chain's segment tree operation costs \(O(\log n)\), so the total time complexity is \(O(n\log n+q\log^2 n)\). In practice, the number of heavy chains rarely reaches \(O(\log n)\) (can be saturated with a complete binary tree), so tree decomposition usually has a small constant.

Reference Code 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <algorithm>
#include <cstring>
#include <iostream>
#define lc o << 1
#define rc o << 1 | 1
constexpr int MAXN = 60010;
constexpr int inf = 2e9;
int n, a, b, w[MAXN], q, u, v;
int cur, h[MAXN], nxt[MAXN], p[MAXN];
int siz[MAXN], top[MAXN], son[MAXN], dep[MAXN], fa[MAXN], dfn[MAXN], rnk[MAXN],
    cnt;
char op[10];

void add_edge(int x, int y) {  // Add edge
  cur++;
  nxt[cur] = h[x];
  h[x] = cur;
  p[cur] = y;
}

struct SegTree {
  int sum[MAXN * 4], maxx[MAXN * 4];

  void build(int o, int l, int r) {
    if (l == r) {
      sum[o] = maxx[o] = w[rnk[l]];
      return;
    }
    int mid = (l + r) >> 1;
    build(lc, l, mid);
    build(rc, mid + 1, r);
    sum[o] = sum[lc] + sum[rc];
    maxx[o] = std::max(maxx[lc], maxx[rc]);
  }

  int query1(int o, int l, int r, int ql, int qr) {  // Query max
    if (l > qr || r < ql) return -inf;
    if (ql <= l && r <= qr) return maxx[o];
    int mid = (l + r) >> 1;
    return std::max(query1(lc, l, mid, ql, qr), query1(rc, mid + 1, r, ql, qr));
  }

  int query2(int o, int l, int r, int ql, int qr) {  // Query sum
    if (l > qr || r < ql) return 0;
    if (ql <= l && r <= qr) return sum[o];
    int mid = (l + r) >> 1;
    return query2(lc, l, mid, ql, qr) + query2(rc, mid + 1, r, ql, qr);
  }

  void update(int o, int l, int r, int x, int t) {  // Update
    if (l == r) {
      maxx[o] = sum[o] = t;
      return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid)
      update(lc, l, mid, x, t);  // Update left and right respectively
    else
      update(rc, mid + 1, r, x, t);
    sum[o] = sum[lc] + sum[rc];
    maxx[o] = std::max(maxx[lc], maxx[rc]);
  }
} st;

void dfs1(int o) {
  son[o] = -1;
  siz[o] = 1;
  for (int j = h[o]; j; j = nxt[j])
    if (!dep[p[j]]) {
      dep[p[j]] = dep[o] + 1;
      fa[p[j]] = o;
      dfs1(p[j]);
      siz[o] += siz[p[j]];
      if (son[o] == -1 || siz[p[j]] > siz[son[o]]) son[o] = p[j];
    }
}

void dfs2(int o, int t) {
  top[o] = t;
  cnt++;
  dfn[o] = cnt;
  rnk[cnt] = o;
  if (son[o] == -1) return;
  dfs2(son[o], t);
  for (int j = h[o]; j; j = nxt[j])
    if (p[j] != son[o] && p[j] != fa[o]) dfs2(p[j], p[j]);
}

int querymax(int x, int y) {  // Query, refer to main function for understanding
  int ret = -inf, fx = top[x], fy = top[y];
  while (fx != fy) {
    if (dep[fx] >= dep[fy])
      ret = std::max(ret, st.query1(1, 1, n, dfn[fx], dfn[x])), x = fa[fx];
    else
      ret = std::max(ret, st.query1(1, 1, n, dfn[fy], dfn[y])), y = fa[fy];
    fx = top[x];
    fy = top[y];
  }
  if (dfn[x] < dfn[y])
    ret = std::max(ret, st.query1(1, 1, n, dfn[x], dfn[y]));
  else
    ret = std::max(ret, st.query1(1, 1, n, dfn[y], dfn[x]));
  return ret;
}

int querysum(int x, int y) {
  int ret = 0, fx = top[x], fy = top[y];
  while (fx != fy) {
    if (dep[fx] >= dep[fy])
      ret += st.query2(1, 1, n, dfn[fx], dfn[x]), x = fa[fx];
    else
      ret += st.query2(1, 1, n, dfn[fy], dfn[y]), y = fa[fy];
    fx = top[x];
    fy = top[y];
  }
  if (dfn[x] < dfn[y])
    ret += st.query2(1, 1, n, dfn[x], dfn[y]);
  else
    ret += st.query2(1, 1, n, dfn[y], dfn[x]);
  return ret;
}

using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i < n; i++) cin >> a >> b, add_edge(a, b), add_edge(b, a);
  for (int i = 1; i <= n; i++) cin >> w[i];
  dep[1] = 1;
  dfs1(1);
  dfs2(1, 1);
  st.build(1, 1, n);
  cin >> q;
  while (q--) {
    cin >> op >> u >> v;
    if (!strcmp(op, "CHANGE")) st.update(1, 1, n, dfn[u], v);
    if (!strcmp(op, "QMAX")) cout << querymax(u, v) << '\n';
    if (!strcmp(op, "QSUM")) cout << querysum(u, v) << '\n';
  }
  return 0;
}

Next is a heavy-light decomposition template problem with root change operations.

LOJ 139. Tree Decomposition

Given a tree with \(n\) nodes (initial root is \(1\)), support \(m\) operations as follows:

  • Change root: set node \(u\) as the new root.
  • Modify path weights: increase the weights of all nodes (including both endpoints) on the path between node \(u\) and node \(v\) by \(w\).
  • Modify subtree weights: increase the weights of all nodes in the subtree rooted at node \(u\) by \(w\).
  • Query path: query the sum of weights of all nodes (including both endpoints) on the path between node \(u\) and node \(v\).
  • Query subtree: query the sum of weights of all nodes in the subtree rooted at node \(u\).

\(1 \le n,m \le 10^5\).

Solution

First, run DFS with \(1\) as the root to precompute the necessary information for tree decomposition. For convenience, the tree with root \(1\) is called the "original tree", and the tree after several root changes is called the "current tree". During operations, maintain \(\textit{root}\) as the root of the current tree. Since the segment tree stores information based on the DFS order of the original tree, each query and modification must be transformed to the original tree.

For root change operations, simply set \(\textit{root}\gets u\). For path operations, since root change does not affect paths, directly perform the corresponding operation on the original tree.

Focus on subtree operations. We classify based on the relative positions of \(u\) and \(\textit{root}\):

  • \(u = \textit{root}\): This is the most special case, equivalent to operating on the entire tree. Thus, directly apply the tag or query the answer on the root of the segment tree.

  • \(u\) is an ancestor of \(\textit{root}\) in the original tree, i.e., \(u\) lies on the simple path from \(1\) to \(\textit{root}\).

    This is the most noteworthy case. Define \(v\) as the node on the simple path from \(u\) to \(\textit{root}\) in the original tree, excluding \(u\), with the smallest depth. It can be observed that the part of the original tree excluding \(v\) and its subtree exactly corresponds to \(u\) and its subtree in the current tree.

    Consider how to efficiently find \(v\). Start with \(v\gets\textit{root}\), then jump up along heavy chains until \(\operatorname{dep}(\operatorname{top}(v))\le\operatorname{dep}(u)+1\).

    • If \(\operatorname{dep}(\operatorname{top}(v))=\operatorname{dep}(u)+1\), set \(v\gets\operatorname{top}(v)\). Now, \(v\) is a light child of \(u\).
    • If \(\operatorname{dep}(\operatorname{top}(v))<\operatorname{dep}(u)+1\), i.e., \(\operatorname{dep}(\operatorname{top}(v))\le \operatorname{dep}(u)\), this means \(u\) and \(v\) are on the same heavy chain. Due to the continuity of DFS order on the same heavy chain, the desired \(v\) must satisfy \(\operatorname{dfn}(v)=\operatorname{dfn}(u)+1\). So, we can set \(v\gets\operatorname{rnk}(\operatorname{dfn}(u)+1)\).

    Note that these two cases can be merged: after jumping, we can directly set

    \[ v\gets\operatorname{rnk}(\operatorname{dfn}(\operatorname{top}(v))+\operatorname{dep}(u)+1-\operatorname{dep}(\operatorname{top}(v))). \]

    It can be verified that the \(v\) found using this expression is equivalent to the \(v\) found by case analysis. The reference implementation uses this expression.

    Since the interval covered by \(v\)'s subtree is \([\operatorname{dfn}(v),\operatorname{dfn}(v)+\operatorname{siz}(v))\), we only need to operate on \([1,\operatorname{dfn}(v))\cup[\operatorname{dfn}(v)+\operatorname{siz}(v),n]\).

  • Other cases. Root change does not affect \(u\)'s subtree, so maintain it normally.

The complexity is the same as the version without root change, \(O(n\log^2 n)\).

Reference Code 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
```cpp
#include <iostream>
#include <vector>

using lint = long long;
constexpr int N = 1e5 + 10;

int n, m, root, a[N];
std::vector<int> G[N];

int idx, fa[N], dep[N], siz[N], son[N], top[N], dfn[N], rnk[N];

struct SegmentTree {  // Segment tree implementation for range add and range sum query
  lint sum[N << 2], lzy[N << 2];

  void maketag(int u, int l, int r, lint x) {
    sum[u] += (r - l + 1) * x;
    lzy[u] += x;
  }

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

  void pushdown(int u, int l, int r) {
    int mid = l + r >> 1;
    maketag(u << 1, l, mid, lzy[u]);
    maketag(u << 1 | 1, mid + 1, r, lzy[u]);
    lzy[u] = 0;
  }

  void build(int u, int l, int r) {
    if (l == r) {
      sum[u] = a[rnk[l]];
      return;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
  }

  void upd(int u, int l, int r, int ql, int qr, lint x) {
    if (ql <= l && r <= qr) {
      maketag(u, l, r, x);
      return;
    }
    int mid = l + r >> 1;
    pushdown(u, l, r);
    if (ql <= mid) upd(u << 1, l, mid, ql, qr, x);
    if (qr > mid) upd(u << 1 | 1, mid + 1, r, ql, qr, x);
    pushup(u);
  }

  lint ask(int u, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return sum[u];
    int mid = l + r >> 1;
    pushdown(u, l, r);
    if (qr <= mid) return ask(u << 1, l, mid, ql, qr);
    if (ql > mid) return ask(u << 1 | 1, mid + 1, r, ql, qr);
    return ask(u << 1, l, mid, ql, qr) + ask(u << 1 | 1, mid + 1, r, ql, qr);
  }
} T;

void dfs1(int u, int f) {  // Heavy-light decomposition preprocessing 1
  fa[u] = f, dep[u] = dep[f] + 1, siz[u] = 1;
  for (auto v : G[u]) {
    if (v == f) continue;
    dfs1(v, u);
    siz[u] += siz[v];
    if (siz[v] > siz[son[u]]) son[u] = v;
  }
}

void dfs2(int u, int tp) {  // Heavy-light decomposition preprocessing 2
  top[u] = tp, dfn[u] = ++idx, rnk[idx] = u;
  if (son[u]) dfs2(son[u], tp);
  for (auto v : G[u])
    if (v != fa[u] && v != son[u]) dfs2(v, v);
}

void modify_path(int u, int v, int w) {  // Standard heavy-light decomposition path modification
  while (top[u] != top[v]) {
    if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
    T.upd(1, 1, n, dfn[top[u]], dfn[u], w);
    u = fa[top[u]];
  }
  if (dep[u] < dep[v]) std::swap(u, v);
  T.upd(1, 1, n, dfn[v], dfn[u], w);
}

void modify_subtree(int u, int w) {
  if (u == root)
    T.maketag(1, 1, n, w);
  else if (dfn[u] <= dfn[root] && dfn[root] <= dfn[u] + siz[u] - 1) {
    int v = root;
    while (dep[top[v]] > dep[u] + 1) v = fa[top[v]];  // Jump up
    v = rnk[dfn[top[v]] + dep[u] + 1 - dep[top[v]]];  // Calculate v
    // The above line can be replaced with the following two lines:
    // if (dep[top[v]] == dep[u] + 1) v = top[v];
    // else if (dep[top[v]] < dep[u] + 1) v = rnk[dfn[u] + 1];
    if (1 <= dfn[v] - 1) T.upd(1, 1, n, 1, dfn[v] - 1, w);
    if (dfn[v] + siz[v] <= n) T.upd(1, 1, n, dfn[v] + siz[v], n, w);
  } else
    T.upd(1, 1, n, dfn[u], dfn[u] + siz[u] - 1, w);
}

lint query_path(int u, int v) {  // Standard heavy-light decomposition path query
  lint res = 0;
  while (top[u] != top[v]) {
    if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
    res += T.ask(1, 1, n, dfn[top[u]], dfn[u]);
    u = fa[top[u]];
  }
  if (dep[u] < dep[v]) std::swap(u, v);
  res += T.ask(1, 1, n, dfn[v], dfn[u]);
  return res;
}

lint query_subtree(int u) {
  if (u == root) return T.sum[1];
  if (dfn[u] <= dfn[root] && dfn[root] <= dfn[u] + siz[u] - 1) {
    int v = root;
    while (dep[top[v]] > dep[u] + 1) v = fa[top[v]];
    v = rnk[dfn[top[v]] + dep[u] + 1 - dep[top[v]]];
    lint res = 0;
    if (1 <= dfn[v] - 1) res += T.ask(1, 1, n, 1, dfn[v] - 1);
    if (dfn[v] + siz[v] <= n) res += T.ask(1, 1, n, dfn[v] + siz[v], n);
    return res;
  }
  return T.ask(1, 1, n, dfn[u], dfn[u] + siz[u] - 1);
}

int main() {
  std::cin.tie(nullptr)->sync_with_stdio(false);
  std::cin >> n, root = 1;
  for (int i = 1; i <= n; ++i) std::cin >> a[i];
  for (int i = 2, f; i <= n; ++i) {
    std::cin >> f;
    G[i].emplace_back(f);
    G[f].emplace_back(i);
  }
  dfs1(1, 0), dfs2(1, 1), T.build(1, 1, n);  // Preprocessing
  for (std::cin >> m; m; --m) {
    int op, u, v, w;
    std::cin >> op >> u;
    if (op == 1)
      root = u;  // Change root
    else if (op == 2)
      std::cin >> v >> w, modify_path(u, v, w);  // Modify path
    else if (op == 3)
      std::cin >> w, modify_subtree(u, w);  // Modify subtree
    else if (op == 4)
      std::cin >> v, std::cout << query_path(u, v) << "\n";  // Query path
    else
      std::cout << query_subtree(u) << "\n";  // Query subtree
  }
  std::cout.flush();
  return 0;
}
```

Finally, an interactive problem, which is a non-traditional application of tree decomposition.

Nauuo and Binary Tree

There is a binary tree rooted at \(1\). You can ask the distance between any two nodes, and you need to find the parent of each node.

The number of nodes is at most \(3000\), and you can ask at most \(30000\) queries.

Solution

First, determine the depth of each node through \(n-1\) queries.

Then, determine the parent of each node in increasing order of depth, so that when determining a node's parent, all its ancestors are already known.

Before determining a node's parent, perform heavy-light decomposition on the known part of the tree.

Suppose we need to locate node \(k\) within the subtree of \(u\). We can ask the distance between \(k\) and the tail of the heavy chain containing \(u\), which further determines the position of \(k\), as shown in the figure:

The red dashed line is a heavy chain, \(d\) is the query result \(\textit{dis}(k, \textit{bot}(u))\), and the depth of \(v\) is \((\textit{dep}(k)+\textit{dep}(\textit{bot}(u))-d)/2\).

Thus, if \(v\) has only one child, then \(k\)'s parent is \(v\); otherwise, recursively find \(k\)'s parent within the subtree of \(w\).

Time complexity \(O(n^2)\), query complexity \(O(n\log n)\).

Specifically, let \(T(n)\) be the worst-case number of queries needed to locate a new node in a tree of size \(n\). We have:

\[ T(n)\le \begin{cases} 0&n=1\\ T\left(\left\lfloor\frac{n-1}2\right\rfloor\right)+1&n\ge2 \end{cases} \]

\(2999+\sum_{i=1}^{2999}T(i)\le 29940\). In fact, this upper bound can be achieved by constructing data, but with some random perturbations (e.g., using an unstable sorting algorithm when sorting by depth), the number of queries rarely exceeds \(21000\).

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

constexpr int N = 3010;

int n, fa[N], ch[N][2], dep[N], siz[N], son[N], bot[N], id[N];

int query(int u, int v) {
  printf("? %d %d\n", u, v);
  fflush(stdout);
  int d;
  scanf("%d", &d);
  return d;
}

void setFather(int u, int v) {
  fa[v] = u;
  if (ch[u][0])
    ch[u][1] = v;
  else
    ch[u][0] = v;
}

void dfs(int u) {
  if (ch[u][0]) dfs(ch[u][0]);
  if (ch[u][1]) dfs(ch[u][1]);

  siz[u] = siz[ch[u][0]] + siz[ch[u][1]] + 1;

  if (ch[u][1])
    son[u] = int(siz[ch[u][0]] < siz[ch[u][1]]);
  else
    son[u] = 0;

  if (ch[u][son[u]])
    bot[u] = bot[ch[u][son[u]]];
  else
    bot[u] = u;
}

void solve(int u, int k) {
  if (!ch[u][0]) {
    setFather(u, k);
    return;
  }
  int d = query(k, bot[u]);
  int v = bot[u];
  while (dep[v] > (dep[k] + dep[bot[u]] - d) / 2) v = fa[v];
  int w = ch[v][son[v] ^ 1];
  if (w)
    solve(w, k);
  else
    setFather(v, k);
}

int main() {
  int i;

  scanf("%d", &n);

  for (i = 2; i <= n; ++i) {
    id[i] = i;
    dep[i] = query(1, i);
  }

  sort(id + 2, id + n + 1, [](int x, int y) { return dep[x] < dep[y]; });

  for (i = 2; i <= n; ++i) {
    dfs(1);
    solve(1, id[i]);
  }

  printf("!");
  for (i = 2; i <= n; ++i) printf(" %d", fa[i]);
  printf("\n");
  fflush(stdout);

  return 0;
}

Long Chain Decomposition

Long chain decomposition is essentially another way of chain decomposition.

Define heavy child as the child with the deepest subtree. If there are multiple children with the deepest subtree, choose one arbitrarily. If there is no child, then there is no heavy child.

Define light child as all remaining children.

The edge from this node to its heavy child is a heavy edge.

Edges to other light children are light edges.

Several heavy edges connected end-to-end form a heavy chain.

Treat isolated nodes as heavy chains as well, so the entire tree is partitioned into several heavy chains.

As shown in the figure (this decomposition can be viewed as either heavy-light decomposition or long chain decomposition):

HLD

The implementation of long chain decomposition is similar to heavy-light decomposition and will not be elaborated here.

Common Applications

First, we note that in long chain decomposition, the number of light edge switches from a node to the root is \(O(\sqrt{n})\).

How to construct data to maximize light edge switches

We can construct a binary tree T as follows:

Let the construction parameter be \(D\).

If \(D \neq 0\), construct a binary tree with parameter \(D-1\) as the left child, and construct a chain of length \(2D-1\) as the right child.

If \(D = 0\), construct a single leaf node and end the call.

This construction ensures that the path from a leaf to the root consists entirely of light edges and requires \(D^2\) nodes.

Set \(D=\sqrt{n}\).

Long Chain Decomposition Optimizing DP

Generally, DP that can be optimized by long chain decomposition has one dimension representing depth.

We can consider using long chain decomposition to optimize tree DP.

Specifically, each node's state directly inherits the state of its heavy child, while merging the DP states of light children by brute force.

Codeforces 1009 F. Dominant Indices

Given a rooted tree with \(n\) vertices, rooted at vertex \(1\).

Define the depth array of vertex \(x\) as an infinite sequence \([d_{x, 0}, d_{x, 1}, d_{x, 2}, \dots]\), where \(d_{x, i}\) denotes the number of vertices \(y\) satisfying:

  • \(x\) is an ancestor of \(y\);
  • The simple path from \(x\) to \(y\) contains exactly \(i\) edges.

The dominant index of vertex \(x\)'s depth array (abbreviated as the dominant index of vertex \(x\)) is defined as an index \(j\) such that:

  • For all \(k < j\), \(d_{x, k} < d_{x, j}\);
  • For all \(k > j\), \(d_{x, k} \le d_{x, j}\).

Compute the dominant index for each vertex in the tree.

Solution

Let \(f_{i,j}\) denote the number of nodes in the subtree of \(i\) at distance \(j\) from \(i\).

Direct brute force DP has time complexity \(O(n^2)\).

We consider that during transfer, we directly inherit the DP array and answer of the heavy child, and update based on that.

First, we need to insert an element 1 at the front of the heavy child's DP array, representing the current node.

Then, we merge the DP arrays of all light children with the current node's DP array by brute force.

Note that the length of a light child's DP array equals the length of the heavy chain containing that light child, and the sum of all heavy chain lengths is \(n\).

That is, the total time complexity of brute force merging light children is \(O(n)\).

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <algorithm>
#include <iostream>
using namespace std;
constexpr int N = 1000005;

struct edge {
  int to, next;
} e[N * 2];

int head[N], tot, n;
int d[N], fa[N], mx[N];
int *f[N], g[N], mxp[N];
int dfn[N];

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

void dfs1(int x) {  // First pass: compute depth and find heavy child
  d[x] = 1;
  for (int i = head[x]; i; i = e[i].next)
    if (e[i].to != fa[x]) {
      fa[e[i].to] = x;
      dfs1(e[i].to);
      d[x] = max(d[x], d[e[i].to] + 1);
      if (d[e[i].to] > d[mx[x]]) mx[x] = e[i].to;
    }
}

void dfs2(int x) {  // Second pass: allocate memory using DFS order
  dfn[x] = ++*dfn;
  f[x] = g + dfn[x];
  if (mx[x]) dfs2(mx[x]);
  for (int i = head[x]; i; i = e[i].next)
    if (e[i].to != fa[x] && e[i].to != mx[x]) dfs2(e[i].to);
}

void getans(int x) {  // Compute answers by merging subtrees
  if (mx[x]) {
    getans(mx[x]);
    mxp[x] = mxp[mx[x]] + 1;
  }
  f[x][0] = 1;
  if (f[x][mxp[x]] <= 1) mxp[x] = 0;
  for (int i = head[x]; i; i = e[i].next)
    if (e[i].to != fa[x] && e[i].to != mx[x]) {
      getans(e[i].to);
      int len = d[e[i].to];
      for (int j = 0; j <= len - 1; j++) {
        f[x][j + 1] += f[e[i].to][j];
        if (f[x][j + 1] > f[x][mxp[x]]) mxp[x] = j + 1;
        if (f[x][j + 1] == f[x][mxp[x]] && j + 1 < mxp[x]) mxp[x] = j + 1;
      }
    }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i < n; i++) {
    int x, y;
    cin >> x >> y;
    add(x, y);
    add(y, x);
  }
  dfs1(1);
  dfs2(1);
  getans(1);
  for (int i = 1; i <= n; i++) cout << mxp[i] << '\n';
}

Note that generally, DP array memory is allocated for an entire heavy chain, with different nodes on the chain having different starting pointers.

The length of the DP array can be determined based on the deepest node in the subtree.

Of course, there are many techniques for long chain decomposition to optimize DP, including but not limited to lazy tags. We will not expand here.

Refer to 租酥雨's blog.

Finding k-th Ancestor with Long Chain Decomposition

That is, given a node, find the node reached by jumping to the parent \(k\) times.

First, assume we have precomputed the \(2^i\)-th ancestors for every node.

Now suppose we have found the \(2^i\)-th ancestor of the query node such that \(2^i \le k < 2^{i+1}\).

We consider finding the nodes on its heavy chain and list them in a table by depth. Let the heavy chain length be \(d\).

Also, during preprocessing, we find the \(1\) to \(d\)-th ancestors of the root of each heavy chain and put them into the table.

By the property of long chain decomposition, \(k-2^i \le 2^i \leq d\), meaning we can \(O(1)\) find the \(k\)-th ancestor of this node from the table of this heavy chain.

Preprocessing requires binary lifting for \(2^i\)-th ancestors and preprocessing the table for each heavy chain.

Preprocessing complexity \(O(n\log n)\), query complexity \(O(1)\).

Exercises

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用