Skip to content

Heavy-Light Decomposition

Introduction

Tree path decomposition splits a tree into chains so that information on tree paths can be maintained.

More precisely, the whole tree is cut into chains, the chains are laid end to end to form a linear structure, and some other data structure maintains the information on it.

Tree path decomposition (or chain decomposition) comes in several forms, such as heavy-light decomposition, long-path decomposition and the decomposition used by the Link/Cut Tree (sometimes called "preferred-path decomposition"). In most cases, unless stated otherwise, "tree path decomposition" means heavy-light decomposition.

Heavy-light decomposition splits any path in the tree into at most \(O(\log n)\) contiguous chains. The nodes on each chain have pairwise distinct depths: the chain runs from bottom to top, and the LCA of all its nodes is one of its endpoints.

Heavy-light decomposition also guarantees that the nodes of each chain are consecutive in DFS order, so a data structure that maintains a sequence (a segment tree, say) can readily maintain information on tree paths. For example:

  1. Update the values of all nodes on the path between two nodes of the tree.
  2. Query the sum, the minimum or maximum, or other information (anything that a data structure can maintain on a sequence and that is easy to merge) of the node weights on the path between two nodes of the tree.

Besides working with a data structure to maintain path information, heavy-light decomposition can find the LCA in \(O(\log n)\) (with a small constant factor). In some problems its properties can be put to more flexible use as well.

Heavy-light decomposition

We start with some definitions.

The heavy child of a node is the child with the largest subtree. If several children tie for the largest subtree, pick any one of them. A node with no children has no heavy child.

All its other children are light children.

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

The edges to its light children are light edges.

A sequence of heavy edges joined end to end forms a heavy path.

Count a node left on its own as a heavy path too, and the whole tree is decomposed into heavy paths.

See the figure:

HLD

Implementation

Heavy-light decomposition is implemented with two DFS passes. In pseudocode:

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 that each node lies on (\(\textit{top}\), which should be initialized to the node itself), the node's index in the DFS order that traverses heavy edges first (\(\textit{dfn}\)), and the node at each index of that 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} \]

Here is an implementation in code.

First, some notation:

  • \(\operatorname{fa}(x)\) is the parent of node \(x\) in the tree.
  • \(\operatorname{dep}(x)\) is the depth of node \(x\) in the tree.
  • \(\operatorname{siz}(x)\) is the number of nodes in the subtree of node \(x\).
  • \(\operatorname{son}(x)\) is the heavy child of node \(x\).
  • \(\operatorname{top}(x)\) is the top node (the one of smallest depth) of the heavy path that contains node \(x\).
  • \(\operatorname{dfn}(x)\) is the index of node \(x\) in the DFS order, which is also its index in the segment tree.
  • \(\operatorname{rnk}(x)\) is the node at a given index of the DFS order, so \(\operatorname{rnk}(\operatorname{dfn}(x))=x\).

Two DFS passes precompute these values: the first computes \(\operatorname{fa}(x)\), \(\operatorname{dep}(x)\), \(\operatorname{siz}(x)\) and \(\operatorname{son}(x)\), and the second computes \(\operatorname{top}(x)\), \(\operatorname{dfn}(x)\) and \(\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 of the tree belongs to exactly one heavy path.

The first node of a heavy path is never a heavy child: it is either the root or a light child of its parent.

Together, the heavy paths decompose the tree completely.

The decomposition traverses heavy edges first, so in the resulting DFS order of the tree the nodes of a heavy path are consecutive. The nodes sorted by DFN are exactly the chains of the decomposition, one after another.

The nodes of a subtree are consecutive in DFS order too.

Whenever we go down a light edge, the size of the subtree we are in is at least halved.

So take any path in the tree and split it at the LCA into two parts that go downward from there. Each part crosses at most \(O(\log n)\) light edges, so every path in the tree can be split into at most \(O(\log n)\) heavy paths.

A principled way to hack heavy-light decomposition

The \(O(\log n)\) factor of heavy-light decomposition is rarely attained in full, which makes it hard to hack: the only way is a binary tree, and a binary tree is shallow.

So we settle for a compromise.

Build a binary tree with \(\sqrt{n}\) nodes, and replace every edge from a node to a child by a chain of length \(\sqrt{n}\).

This pushes the number of chain switches of a random query up to \(\frac{\log n}{2}\) on average, while the depth is \(O(\sqrt{n} \log n)\).

Add a few random leaves and this looks able to hack heavy-light decomposition. But the constant factor is small, so it may well survive.

Common applications

Maintaining information on paths

The following pseudocode uses heavy-light decomposition to compute the sum of the weights on the path between two nodes of a tree:

\[ \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 nodes of a chain are consecutive in DFS order, so a segment tree or a Fenwick tree can maintain them.

At each step, jump up from the deeper of the two chains, until both nodes are on the same chain.

The same chain-jumping structure works for maintaining or collecting any other information on a path.

Maintaining information on subtrees

Some problems ask us to maintain information on subtrees, for example to add \(v\) to the weight of every node in the subtree rooted at \(x\).

During the DFS, the nodes of a subtree receive consecutive indices in the DFS order.

Each node records bottom, the last node of the contiguous range that its subtree occupies.

Information on a subtree thus becomes information on one contiguous range.

Finding the lowest common ancestor

Keep jumping up heavy paths. Once both nodes are on the same heavy path, the shallower one is the LCA.

At each jump, move the node whose heavy path has the deeper top.

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;
}

Rerooting

Consider a new kind of problem: in addition to the basic operations that heavy-light decomposition supports, there is a reroot operation.

The information that heavy-light decomposition maintains is static and cannot be changed on the fly. Nor can we redo the preprocessing after every reroot: that would be far too slow. We have to make full use of what was computed earlier to handle rerooting.

Path updates and queries do not change: the simple path between two nodes of a tree is unique, so they are handled as usual.

For subtree updates and queries, the usual idea is to map a subtree of the rerooted tree onto subtrees of the original tree. This takes a case analysis on the relative positions of three nodes: the root of the subtree being operated on, the root of the whole tree after rerooting, and the root of the original tree. For the details, see the example problem "LOJ 139. Heavy-Light Decomposition" below.

Example problems

The example problems below show how heavy-light decomposition is applied. The first is a template problem.

[ZJOI2008] Tree Statistics

On a static tree with \(n\) nodes, each carrying a weight, perform \(q\) operations of three kinds:

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

It is guaranteed that \(1\le n\le 30000\) and \(0\le q\le 200000\).

Solution

By the problem statement and the properties above, the segment tree has to support three operations:

  1. point update;
  2. range query for the maximum;
  3. range query for the sum.

Point updates are easy to implement.

The nodes of a subtree are consecutive in DFS order (with or without heavy-light decomposition), so updating the subtree of a node only means updating that one contiguous range of the DFS order.

The question is how to update or query the path between two nodes.

Recall how we find the LCA by binary lifting: we first bring the two nodes to the same height, then make both jump up together. The same idea works with heavy-light decomposition.

While jumping up, if the current node is on a heavy path, jump to the top of that heavy path; if it is not on a heavy path, jump up by one node. Go on until the two nodes are the same, updating or querying range information along the way.

Each query passes through at most \(O(\log n)\) heavy paths, and the segment tree costs \(O(\log n)\) on each of them, so the total time complexity is \(O(n\log n+q\log^2 n)\). In practice the number of heavy paths rarely gets to \(O(\log n)\) (a complete binary tree attains the bound), so heavy-light decomposition usually has a small constant factor.

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 an 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 the 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 the 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 the left or the right child
    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; see the main function to understand it
  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 template problem for heavy-light decomposition with rerooting.

LOJ 139. Heavy-Light Decomposition

Given a tree with \(n\) nodes (the root is initially node \(1\)), support \(m\) operations of the following kinds:

  • Reroot: make node \(u\) the new root of the tree.
  • Path update: add \(w\) to the weight of every node on the path between node \(u\) and node \(v\) (both included).
  • Subtree update: add \(w\) to the weight of every node in the subtree rooted at node \(u\).
  • Path query: report the sum of the weights of all nodes on the path between node \(u\) and node \(v\) (both included).
  • Subtree query: report the sum of the weights of all nodes in the subtree rooted at node \(u\).

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

Solution

First run the DFS with \(1\) as the root and precompute everything heavy-light decomposition needs. For convenience, call the tree rooted at \(1\) the "original tree" and the tree after some number of reroot operations the "current tree". Throughout, maintain \(\textit{root}\), the root of the current tree. The segment tree stores its information in the DFS order of the original tree, so every query or update on the current tree has to be converted into operations on the original tree.

For a reroot operation, just set \(\textit{root}\gets u\). Rerooting does not affect paths, so path operations are carried out directly on the original tree.

The subtree operations are where the work lies. We distinguish cases by the relative position of \(u\) and \(\textit{root}\):

  • \(u = \textit{root}\): the most special case, which amounts to operating on the whole tree. Just apply a tag to the root of the segment tree, or read the answer from it.
  • \(u\) is an ancestor of \(\textit{root}\) in the original tree, that is, \(u\) lies on the simple path from \(1\) to \(\textit{root}\).

    This is the case that needs the most care. Let \(v\) be the node of smallest depth, other than \(u\), on the simple path from \(u\) to \(\textit{root}\) in the original tree. Then the part of the original tree outside \(v\) and its subtree is exactly \(u\) and its subtree in the current tree.

    How do we find \(v\) efficiently? Start with \(v\gets\textit{root}\), then jump up along heavy paths 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\), that is, \(\operatorname{dep}(\operatorname{top}(v))\le \operatorname{dep}(u)\), then \(u\) and \(v\) are on the same heavy path. A heavy path is consecutive in DFS order, so the \(v\) we want must satisfy \(\operatorname{dfn}(v)=\operatorname{dfn}(u)+1\), and we can set \(v\gets\operatorname{rnk}(\operatorname{dfn}(u)+1)\).

    The two cases can be merged: once the jumping is done, set

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

    It is easy to check that this expression gives the same \(v\) as the case analysis. The reference implementation uses it.

    The subtree of \(v\) covers the range \([\operatorname{dfn}(v),\operatorname{dfn}(v)+\operatorname{siz}(v))\), so it is enough to operate on \([1,\operatorname{dfn}(v))\cup[\operatorname{dfn}(v)+\operatorname{siz}(v),n]\).

  • All other cases. Rerooting does not affect the subtree of \(u\), so handle it in the usual way.

The complexity is the same as without rerooting: \(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
#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 with range add and range sum
  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) {  // HLD preprocessing, pass 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) {  // HLD preprocessing, pass 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) {  // ordinary HLD
  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]]];  // compute v
    // The statement above can be replaced by the following two:
    // 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) {  // ordinary HLD
  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;  // reroot
    else if (op == 2)
      std::cin >> v >> w, modify_path(u, v, w);  // path update
    else if (op == 3)
      std::cin >> w, modify_subtree(u, w);  // subtree update
    else if (op == 4)
      std::cin >> v, std::cout << query_path(u, v) << "\n";  // path query
    else
      std::cout << query_subtree(u) << "\n";  // subtree query
  }
  std::cout.flush();
  return 0;
}

The last one is an interactive problem, and an unconventional use of heavy-light decomposition.

Nauuo and Binary Tree

There is a binary tree rooted at \(1\). You may ask for the distance between any two nodes. Find the parent of every node.

The tree has at most \(3000\) nodes, and you may make at most \(30000\) queries.

Solution

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

Then determine the parents in increasing order of depth, so that when we look for the parent of a node, all its ancestors are already known.

Before determining the parent of a node, compute the heavy-light decomposition of the part of the tree known so far.

Suppose we need to locate node \(k\) inside the subtree of \(u\). Query the distance between \(k\) and the bottom end of the heavy path containing \(u\); this narrows down where \(k\) is, as the figure shows:

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

If \(v\) has only one child, then \(v\) is the parent of \(k\); otherwise, recurse into the subtree of \(w\) to find the parent of \(k\).

This takes \(O(n^2)\) time and \(O(n\log n)\) queries.

More precisely, let \(T(n)\) be the number of queries needed in the worst case to locate a new node in a tree of size \(n\). Then

\[ 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\), and this upper bound can in fact be attained by constructed test data. With a little random perturbation, however (such as sorting by depth with an unstable sorting algorithm), the number of queries will hardly ever exceed \(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-path decomposition

Long-path decomposition is, in essence, just another way to decompose a tree into chains.

The heavy child of a node is the child whose subtree is deepest. If several children tie for the deepest subtree, pick any one of them. A node with no children has no heavy child.

Its remaining children are light children.

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

The edges to its light children are light edges.

A sequence of heavy edges joined end to end forms a heavy path.

Count a node left on its own as a heavy path too, and the whole tree is decomposed into heavy paths.

See the figure (this decomposition can be read both as a heavy-light decomposition and as a long-path decomposition):

HLD

Long-path decomposition is implemented much like heavy-light decomposition, so we do not spell it out here.

Common applications

First, under long-path decomposition the path from a node to the root crosses on the order of \(\sqrt{n}\) light edges.

How to construct test data that attains the bound on light/heavy edge switches

Construct a binary tree T as follows:

Let the tree have a parameter \(D\).

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

If \(D = 0\), build a single leaf and end the recursion.

In a tree built this way, the path from that single leaf to the root consists entirely of light edges, and the tree needs on the order of \(D^2\) nodes.

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

Optimizing DP with long-path decomposition

A DP that long-path decomposition can optimize usually has depth as one dimension of its state.

We can use long-path decomposition to optimize DP on trees.

Specifically, each node inherits its state directly from its heavy child, and the DP states of its light children are merged in by brute force.

Codeforces 1009 F. Dominant Indices

You are given a rooted tree with \(n\) vertices, rooted at vertex \(1\).

The depth array of vertex \(x\) is the infinite sequence \([d_{x, 0}, d_{x, 1}, d_{x, 2}, \dots]\), where \(d_{x, i}\) is the number of vertices \(y\) that satisfy both of the following conditions:

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

The dominant index of the depth array of vertex \(x\) (the dominant index of vertex \(x\) for short) is an index \(j\) such that:

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

Compute the dominant index of every vertex of the tree.

Solution

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

Brute-force transitions take \(O(n^2)\) time.

Instead, at each transition we inherit the DP array and the answer of the heavy child and update them from there.

First, insert an element 1 at the front of the heavy child's DP array; it stands for the current node.

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

The DP array of a light child is as long as the heavy path that the light child is on, and the lengths of all heavy paths add up to \(n\).

So merging the light children by brute force takes \(O(n)\) time in total.

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: insert a 1
  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: merge
  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) {  // merge by brute force and compute the answer
  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 memory for the DP arrays is normally allocated one whole heavy path at a time; each node on the path has its own pointer to where its array starts.

The length of a DP array can be computed from the deepest node of the subtree.

There are of course many more tricks for optimizing DP with long-path decomposition, including but not limited to applying tags. We do not go into them here.

See zhoushuyu's blog (in Chinese).

Finding the k-th ancestor with long-path decomposition

That is, we are asked for the node reached from a given node by jumping to the parent \(k\) times.

Assume first that we have precomputed the \(2^i\)-th ancestor of every node.

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

Take the nodes of the heavy path that this ancestor is on and list them in a table by depth. Let the length of the heavy path be \(d\).

During preprocessing we also find the \(1\)st to \(d\)-th ancestors of the top of each heavy path and put them in a table as well.

By the property of long-path decomposition, \(k-2^i \le 2^i \leq d\), so the \(k\)-th ancestor of the node can be read off the tables of this heavy path in \(O(1)\).

Preprocessing has to compute the \(2^i\)-th ancestors by binary lifting, and also the tables of every heavy path.

Preprocessing takes \(O(n\log n)\) and each query \(O(1)\).

Practice problems