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:
- Update the values of all nodes on the path between two nodes of the tree.
- 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:
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}\)).
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}\)).
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 | |
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:
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 | |
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:
- update the weight of a single node;
- query the maximum weight on the path from \(u\) to \(v\);
- 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:
- point update;
- range query for the maximum;
- 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 | |
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 | |
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
\(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 | |
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):
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 | |
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
- Luogu P3379 [Template] Lowest Common Ancestor (LCA) (finding the LCA with heavy-light decomposition needs no data structure, so this makes a good exercise)
- [JLOI2014] The Squirrel's New Home (difference on trees works too, of course)
- [HAOI2015] Operations on a Tree
- Luogu P3384 [Template] Heavy-Light Decomposition / Tree Path Decomposition
- Luogu P1505 [Chinese national training team] Tourism
- [NOI2015] Package Manager
- [SDOI2011] Coloring
- [SDOI2014] Travel
- Luogu P3979 A Faraway Country
- [POI2014] Hotel, Harder Version (optimizing DP with long-path decomposition)
- Strategy Guide (optimizing a greedy algorithm with long-path decomposition)
This page is an unofficial English translation of the original OI Wiki page (revision 9bb3a8e6), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: GoodCoder666, Ir1d, Marcythm, ouuan, hsfzLZH1, Xeonacid, greyqz, Chrogeek, ftxj, sshwy, LuoshuiTianyi, hyp1231, sun2snow, Desmos666-xh, 24OI-bot, zhouyuyang2002, StudyingFather, 2997ms, Early0v0, zirnc, Henry-ZHR, H-J-Granger, fearlessxjdx, mao1t, Enter-tainer, kenlig, ksyx, Macesuted, Alexander-a-l, Great-designer, Tiphereth-A, Menci, CCXXXI, Molmin, amlhdsan, c-forrest, HeRaNO, LiserverYang, forever516-hack (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.