AIOJ

Introduction

Tree-chain decomposition splits a tree into several chains so that information on paths in the tree can be maintained.

More specifically, it decomposes the whole tree into several chains, making it into a linear structure, and then uses another data structure to maintain the information.

Tree-chain decomposition (also called tree decomposition or chain decomposition) has several forms, including heavy-light decomposition, long-chain decomposition, and the decomposition used for Link/cut Trees (sometimes called “real-chain decomposition”). Unless otherwise specified, “tree-chain decomposition” generally refers to heavy-light decomposition.

Heavy-light decomposition can divide any path in a tree into at most $O(\log n)$ contiguous chains. The vertices on each chain have distinct depths (that is, each chain runs upward from the bottom, and the LCA of all vertices on the chain is one endpoint).

Heavy-light decomposition also guarantees that the vertices on each chain have consecutive DFS orderings, making it convenient to maintain path information with data structures for sequences, such as segment trees. For example:

Modify the values of all vertices on the path between two vertices in the tree.
Query the sum, extremum, or other mergeable information of the vertex weights on the path between two vertices in the tree.

Besides working with data structures to maintain path information, tree-chain decomposition can find the LCA in $O(\log n)$ time (with a small constant). Its properties can also be used flexibly in some problems.

Heavy-light decomposition

We first give some definitions:

A heavy child is a child whose subtree is largest among all children. If several children have the largest subtree, choose any one. If there are no children, there is no heavy child.

A light child is any of the remaining children.

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

An edge to another light child is a light edge.

Several consecutive heavy edges form a heavy chain.

Treating an isolated vertex as a heavy chain as well, the whole tree is decomposed into several heavy chains.

As shown in the figure:

HLD

Implementation

The implementation of tree-chain decomposition consists of two DFS passes. The pseudocode is as follows:

The first DFS records each vertex'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 containing each vertex ( $\textit{top}$ , initialized to the vertex itself), the DFS order obtained by visiting heavy edges first ( $\textit{dfn}$ ), and the vertex corresponding to each 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 implementation is shown below.

We first give some definitions:

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

We preprocess these values with two DFS passes. The first computes $\operatorname{fa}(x)$ , $\operatorname{dep}(x)$ , $\operatorname{siz}(x)$ , and $\operatorname{son}(x)$ ; the second computes $\operatorname{top}(x)$ , $\operatorname{dfn}(x)$ , and $\operatorname{rnk}(x)$ .

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 vertex in the tree belongs to exactly one heavy chain.

The first vertex of a heavy chain is never a heavy child, because it is either the root or a light child of its parent.

All heavy chains completely decompose the whole tree.

During decomposition, visiting heavy edges first makes the DFS orders within each heavy chain consecutive. Sorting by DFN therefore gives the chains produced by the decomposition.

The DFS orders within a subtree are consecutive.

Whenever we move downward across a light edge, the size of the current subtree is at least halved.

Therefore, split any path in the tree at its LCA into two downward paths. Each side crosses at most $O(\log n)$ light edges, so every tree path can be divided into at most $O(\log n)$ heavy chains.

How to construct a worst case for heavy-light decomposition

In general, the constant in the $O(\log n)$ complexity of heavy-light decomposition is difficult to maximize. If we want to force a bad case, we can build a binary tree with small depth.

Consider a compromise. Build a binary tree with $\sqrt{n}$ vertices, and replace every edge from a vertex to a child with a chain of length $\sqrt{n}$ .

This makes the average number of heavy-light switches in random queries reach $\frac{\log n}{2}$ , while the depth is $O(\sqrt{n} \log n)$ .

Adding several random leaves may appear to defeat heavy-light decomposition, but its small constant may still prevent this.

Common applications

Maintaining paths

The following is pseudocode for using heavy-light decomposition to find the sum of weights on a path between two vertices:

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

DFS orders on a chain are consecutive, so segment trees or Fenwick trees can maintain them.

Each time, choose the chain with the greater depth and jump upward until the two vertices lie on the same chain.

The same chain-jumping structure applies to maintaining and aggregating other path information.

Maintaining subtrees

Sometimes we need to maintain subtree information, such as increasing the weights of all vertices in the subtree rooted at $x$ by $v$ .

During the DFS, the vertices in a subtree have consecutive DFS orders.

For each vertex, record bottom as the vertex at the end of the contiguous interval of its subtree.

This converts subtree information into information on one contiguous interval.

Finding the lowest common ancestor

Keep jumping upward by heavy chains. Once both vertices are on the same heavy chain, the one with smaller depth is the LCA.

When jumping upward by heavy chains, first jump from the chain whose top has greater depth.

Reference code:

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 class of problems that adds rerooting operations to the basic operations supported by heavy-light decomposition.

The information maintained by heavy-light decomposition is static and does not support dynamic changes. At the same time, recomputing the preprocessing after every rerooting is too expensive. We therefore need to make full use of the information already obtained to handle rerooting.

Path modification and query operations do not change, because the simple path between two vertices in a tree is unique; they are handled as usual.

For subtree modification and query operations, the general idea is to map a subtree after rerooting back to a subtree in the original tree. This requires case analysis based on the relative positions of the operated subtree's root, the root of the whole tree after rerooting, and the original root. See the example later in this article for details.

Example problems

This article demonstrates applications of heavy-light decomposition through examples. We begin with a template problem.

「ZJOI2008」Tree Statistics

On a static tree with $n$ vertices carrying weights, support the following three operations, performed $q$ times:

Modify the weight of a single vertex;
Query the maximum weight on the path from $u$ to $v$ ;
Query the sum of weights on the path from $u$ to $v$ .

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

Solution

According to the problem statement and the properties described above, the segment tree needs to support three operations:

Point modification;
Range maximum query;
Range sum query.

Point modification is easy to implement.

Because a subtree's DFS orders are consecutive (regardless of whether heavy-light decomposition is used), modifying a vertex's subtree only requires modifying one contiguous DFS-order interval.

The question is how to modify or query the path between two vertices.

Consider how binary lifting finds the LCA. First, raise the two vertices to the same height, then move both vertices upward together. Heavy-light decomposition can use the same idea.

While moving upward, if the current vertex is on a heavy chain, jump to the top of that chain; otherwise, jump up by one vertex. Continue until the two vertices coincide, updating or querying interval information along the way.

Each query passes through at most $O(\log n)$ heavy chains, and the segment-tree complexity on each chain is $O(\log n)$ , so the total time complexity is $O(n\log n+q\log^2 n)$ . In practice, it is difficult for the number of heavy chains to reach $O(\log n)$ (a complete binary tree can force this), so heavy-light decomposition usually has a small constant.

Reference code

#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 the left and right sides separately
    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 for context
  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 rerooting operations.

LOJ 139. Heavy-light decomposition

Given a tree with $n$ vertices (initially rooted at $1$ ), support the following $m$ operations:

Reroot the tree, making vertex $u$ the new root.
On the path from $u$ to $v$ , add $w$ to every vertex (including both endpoints).
In the subtree rooted at $u$ , add $w$ to every vertex.
Query the sum of weights of all vertices (including both endpoints) on the path from $u$ to $v$ .
Query the sum of weights of all vertices in the subtree rooted at $u$ .

$1 \le n,m \le 10^5$ .

Solution

First run DFS with $1$ as the root and preprocess the information required by heavy-light decomposition. For convenience, call the tree rooted at $1$ the “original tree”, and the tree after one or more rerooting operations the “current tree”. During the operations, maintain $\textit{root}$ as the root of the current tree. For a rerooting operation, set $\textit{root}\gets u$ directly. Path operations are unaffected by rerooting and can be performed on the original tree.

The key issue is subtree operations. We analyze cases according to the relative positions of $u$ and $\textit{root}$ :

$u = \textit{root}$ : This is the special case equivalent to operating on the entire tree. Apply a tag to the segment-tree root or query its answer directly.
$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 most important case. Let $v$ be the shallowest vertex on the simple path from $u$ to $\textit{root}$ , other than $u$ . The part of the original tree outside $v$ and its subtree is exactly the subtree of $u$ in the current tree.

To find $v$ efficiently, first set $v\gets\textit{root}$ , then jump upward 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)$ . Then $v$ is a light child of $u$ .
- If $\operatorname{dep}(\operatorname{top}(v))<\operatorname{dep}(u)+1$ , equivalently $\operatorname{dep}(\operatorname{top}(v))\le \operatorname{dep}(u)$ , then $u,v$ lie on the same heavy chain. Since DFS orders on one heavy chain are consecutive, the required $v$ satisfies $\operatorname{dfn}(v)=\operatorname{dfn}(u)+1$ . Thus set $v\gets\operatorname{rnk}(\operatorname{dfn}(u)+1)$ .
These two cases can be combined. After jumping, set
$v\gets\operatorname{rnk}(\operatorname{dfn}(\operatorname{top}(v))+\operatorname{dep}(u)+1-\operatorname{dep}(\operatorname{top}(v))).$
It is easy to verify that the $v$ found by this expression is equivalent to the $v$ found by the case analysis. The reference implementation uses this expression.

Since the interval covered by the subtree of $v$ 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. Rerooting does not affect the subtree of $u$ , so maintain it normally.

This has the same complexity as the version without rerooting, namely $O(n\log^2 n)$ .

Reference code

#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 for range addition and range-sum queries
  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 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 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
  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 upward
    v = rnk[dfn[top[v]] + dep[u] + 1 - dep[top[v]]];  // Compute v
    // The preceding line can be replaced by 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
  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);  // Preprocess
  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);  // 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, showing a nontraditional application of tree-chain decomposition.

Nauuo and Binary Tree

A binary tree rooted at $1$ is given. You may query the distance between any two vertices; determine the parent of every vertex.

The number of vertices is at most $3000$ , and you may make at most $30000$ queries.

Solution

First, determine the depth of every vertex using $n-1$ queries.

Then determine the parent of each vertex in increasing order of depth. When determining a vertex's parent, all of its ancestors are already known.

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

Suppose we need to find the position in subtree $u$ of vertex $k$ . Query the distance from $k$ to the end of the heavy chain containing $u$ ; then determine the position of $k$ ; see the figure:

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

If $v$ has only one child, then the parent of $k$ is $v$ ; otherwise, recursively find the parent in the subtree of $w$ for $k$ .

The time complexity is $O(n^2)$ and the query complexity is $O(n\log n)$ .

More precisely, let $T(n)$ be the number of queries needed in the worst case to locate a new vertex 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$ . This upper bound can in fact be attained by a constructed input, but with some random perturbation (such as using an unstable sort when sorting by depth), the number of queries is unlikely to exceed $21000$ .

Reference code

#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 form of chain decomposition.

A heavy child is a child whose subtree has the greatest depth. If several children have the greatest subtree depth, choose any one. If there are no children, there is no heavy child.

A light child is any of the remaining children.

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

An edge to another light child is a light edge.

Several consecutive heavy edges form a heavy chain.

Treating an isolated vertex as a heavy chain as well, the whole tree is decomposed into several heavy chains.

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

HLD

The implementation of long-chain decomposition is similar to that of heavy-light decomposition, so we do not expand on it here.

Common applications

First, we observe that the number of light-edge switches on a path from a vertex to the root under long-chain decomposition is on the order of $\sqrt{n}$ .

How to construct data that maximizes light-heavy switches

We can construct a binary tree T as follows:

Let the parameter of the constructed binary tree be $D$ .

If $D \neq 0$ , construct 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$ , construct a single leaf vertex and end the recursion.

This construction makes every edge on the path from the isolated leaf to the root a light edge, and uses on the order of $D^2$ vertices.

Taking $D=\sqrt{n}$ suffices.

Using long-chain decomposition to optimize DP

In general, DP optimized by long-chain decomposition has one dimension representing depth.

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

Specifically, each vertex directly inherits the DP state of its heavy child, and then merges the DP states of its 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 the infinite sequence $[d_{x, 0}, d_{x, 1}, d_{x, 2}, \dots]$ , where $d_{x, i}$ is the number of vertices $y$ satisfying:

$x$ is an ancestor of $y$ ;
the simple path from $x$ to $y$ has exactly $i$ edges.

The dominant index of the depth array of vertex $x$ is an index for vertex $x$ , namely $j$ satisfying:

For every $k < j$ , $d_{x, k} < d_{x, j}$ ;
For every $k > j$ , $d_{x, k} \le d_{x, j}$ .

Compute the dominant index of every vertex in the tree.

Solution

Let $f_{i,j}$ be the number of vertices in subtree i whose distance from i is j.

A direct brute-force transition takes $O(n^2)$ time.

For each transition, inherit the DP array and answer of the heavy child directly, then update them.

First insert an element 1 at the front of the heavy child's DP array to represent the current vertex.

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

Since the length of a light child's DP array equals the length of the heavy chain containing that light child, and the sum of the lengths of all heavy chains is $n$ , the total time for brute-force merging the light children is $O(n)$ .

Reference code

#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 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) {  // Merge the second time
  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) {  // Brute-force merge to 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';
}

In general, memory for a DP array is allocated for an entire heavy chain, and different vertices on the chain have pointers to different starting positions.

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

There are many other long-chain decomposition techniques for optimizing DP, including but not limited to applying tags; we do not elaborate here.

See Zhuo Suyu's blog.

Finding the k-th ancestor with long-chain decomposition

That is, query the vertex reached after moving $k$ times toward a vertex's parent.

Assume that the $2^i$ -th ancestor of every vertex has already been preprocessed.

Suppose we have found the queried vertex's $2^i$ -th ancestor satisfying $2^i \le k < 2^{i+1}$ .

We find the vertices on its heavy chain and place them in a table ordered by depth. Let the heavy-chain length be $d$ .

During preprocessing, we also find the $1$ -st through $d$ -th ancestors of the root of every heavy chain and place them in a table.

By the properties of long-chain decomposition, $k-2^i \le 2^i \leq d$ , so the ancestor on this heavy chain can be found in $O(1)$ time as the ancestor at distance $k$ .

Preprocessing requires binary lifting for the $2^i$ -th ancestors, as well as preprocessing the table corresponding to every heavy chain.

The preprocessing complexity is $O(n\log n)$ , and the query complexity is $O(1)$ .

Exercises

“Luogu P3379” (Template) Lowest Common Ancestor (LCA) (tree-chain decomposition can find the LCA without a data structure, so this is useful practice)
“JLOI2014” Squirrel's New Home (tree difference can also be used)
“HAOI2015” Operations on a Tree
“Luogu P3384” (Template) Heavy-light decomposition / tree-chain decomposition
“Luogu P1505” \[National Training Team\] Travel
“NOI2015” Package Manager
“SDOI2011” Coloring
“SDOI2014” Travel
“Luogu P3979” Distant Country
“POI2014” Hotel Enhanced (DP optimized with long-chain decomposition)
Guide (greedy optimization with long-chain decomposition)

Heavy-light Decomposition

Introduction

Heavy-light decomposition

Implementation

Properties of heavy-light decomposition

Common applications

Maintaining paths

Maintaining subtrees

Finding the lowest common ancestor

Rerooting

Example problems

Long-chain decomposition

Common applications

Using long-chain decomposition to optimize DP

Finding the k-th ancestor with long-chain decomposition

Exercises