### Al.Cash's blog

By Al.Cash, history, 4 years ago, ,

Recently I've been looking for a good heavy-light decomposition code I can just copy-paste and continue to live happily. To my greatest disappointment, I didn't find one and had to write my own.

First, there's this blog explaining what HLD is http://blog.anudeep2011.com/heavy-light-decomposition/, but it doesn't contain full code. Also it uses LCA for queries, which is absolutely unnecessary and complicates things too much.

Second, there's this implementation https://sites.google.com/site/indy256/algo/heavy_light. (It has been updated, so the comment is related to old version). OK, complete working code, and it doesn't use LCA. But it has too many arrays. Way too many! Also it's mixed with segment tree code, and I'd rather separate the logic.

Third, there's this post http://apps.topcoder.com/forums/?module=Thread&threadID=796128&start=0&mc=8. So far the best looking code, but it has only LCA method and no path query handling, which is the point of HLD. So, I refined the code and added missing parts.

The code is probably too simple to explain it, but not well tested yet. Graph can be represented for example as vector<vector<int>>. I use single segment tree for all the chains. Creating separate trees makes code harder to read and also slower (at least in my experiment). For a good segment tree implementation you can look here: http://codeforces.com/blog/entry/18051.

template <class T, int V>
class HeavyLight {
int parent[V], heavy[V], depth[V];
int root[V], treePos[V];
SegmentTree<T> tree;

template <class G>
int dfs(const G& graph, int v) {
int size = 1, maxSubtree = 0;
for (int u : graph[v]) if (u != parent[v]) {
parent[u] = v;
depth[u] = depth[v] + 1;
int subtree = dfs(graph, u);
if (subtree > maxSubtree) heavy[v] = u, maxSubtree = subtree;
size += subtree;
}
return size;
}

template <class BinaryOperation>
void processPath(int u, int v, BinaryOperation op) {
for (; root[u] != root[v]; v = parent[root[v]]) {
if (depth[root[u]] > depth[root[v]]) swap(u, v);
op(treePos[root[v]], treePos[v] + 1);
}
if (depth[u] > depth[v]) swap(u, v);
op(treePos[u], treePos[v] + 1);
}

public:
template <class G>
void init(const G& graph) {
int n = graph.size();
fill_n(heavy, n, -1);
parent[0] = -1;
depth[0] = 0;
dfs(graph, 0);
for (int i = 0, currentPos = 0; i < n; ++i)
if (parent[i] == -1 || heavy[parent[i]] != i)
for (int j = i; j != -1; j = heavy[j]) {
root[j] = i;
treePos[j] = currentPos++;
}
tree.init(n);
}

void set(int v, const T& value) {
tree.set(treePos[v], value);
}

void modifyPath(int u, int v, const T& value) {
processPath(u, v, [this, &value](int l, int r) { tree.modify(l, r, value); });
}

T queryPath(int u, int v) {
T res = T();
processPath(u, v, [this, &res](int l, int r) { res.add(tree.query(l, r)); });
return res;
}
};


• +323

 » 4 years ago, # |   +10 Hi, first of all, awesome implementation. I have a doubt about this part of the code void processPath(int u, int v, BinaryOperation op) { for (; root[u] != root[v]; v = parent[root[v]]) { if (depth[root[u]] > depth[root[v]]) swap(u, v); op(treePos[root[v]], treePos[v] + 1); } if (depth[u] > depth[v]) swap(u, v); op(treePos[u], treePos[v] + 1); // This particular line } Let's assume that the path (u, v) is in the same chain, if we query the range [treePos[u], treePos[v] + 1), then we will be considering whatever cost the node u has to its parent (and we shouldn't).Thinking about that, I came up with this: void processPath(int u, int v, BinaryOperation op) { for (; root[u] != root[v]; v = parent[root[v]]) { if (depth[root[u]] > depth[root[v]]) swap(u, v); op(treePos[root[v]], treePos[v] + 1); } if (depth[u] > depth[v]) swap(u, v); op(treePos[heavy[u]], treePos[v] + 1); // If we go to the next node in the chain, we avoid considering edge (parent of u, u) } I am not an expert in HLD, so I may be wrong :)
•  » » 4 years ago, # ^ |   +3 Good point. I forgot to mention that I consider values to be stored in vertices. I believe the other case (values on edges) can be handled similarly to indy256's approach by changing the line to  op(treePos[u] + (VALUES_IN_VERTICES ? 0 : 1), treePos[v] + 1); 
•  » » » 21 month(s) ago, # ^ |   +3 I tried this, but this didn't work for the USACO problem grassplant. It also didn't work when I used the original implementation for Timus 1553. I'm pretty sure it's not my segment tree that's wrong since I've verified it on many problems.
•  » » 4 years ago, # ^ |   0 HLD supports updating the tree unlike the LCA sparse array approach.
•  » » » 4 years ago, # ^ |   0 Updating weights or something like that, right? But the topology must remain the same, right?
•  » » » » 4 years ago, # ^ |   0 Yes. The tree structure is fixed.
 » 4 years ago, # |   0 Could you please explain this: [this, &value](int l, int r) { tree.modify(l, r, value); } [this, &res](int l, int r) { res.add(tree.query(l, r)); } What does the program modify path, get the answer?
•  » » 4 years ago, # ^ |   +3 These are C++11 lambda functions I used to avoid code duplication. Basically the code in brackets will substitute calls to BinaryOperation op. This code may depend on segment tree implementation and the result type, but I hope it gives the general idea.
 » 4 years ago, # |   +21 I have rewritten my Java implementation https://sites.google.com/site/indy256/algo/heavy_light using your neat code (if you are not against). Old version is here.
•  » » 4 years ago, # ^ |   +16 Sure, thank you for the useful library. Though it would be nice to have a link like Sleator has https://sites.google.com/site/indy256/algo/link-cut-tree-connectivity
 » 4 years ago, # | ← Rev. 2 →   0 Why do you use one SegmentTree for all operations? Isn't it going to slow down the code in the most cases? You are not using cache (tree is too big) and even log is bigger.I've never seen the code without lca and it's really cool. But still in most problems you just need lca for the purposes of counting some weird functions.
•  » » 4 years ago, # ^ |   +1 I do because it's easier!Also it's faster for single element updates and path queries using non-recursive segment tree. Multiple trees may be faster when lazy propagation is needed, but I don't think more than 10% faster if any. Time limits for problems requiring HLD aren't usually strict anyway. And non-recursive segment tree vs recursive is much more significant improvement.I don't know how are you going to use cache when you need to access O(logN) different trees per query.This code implicitly finds LCA and it's node u at the end of processPath method. You can just return it if you need it.
 » 21 month(s) ago, # | ← Rev. 2 →   +3 Are you sure this is right? I implemented it for Timus 1553 (http://acm.timus.ru/problem.aspx?space=1&num=1553&locale=en), but for some reason got WA on test case 4. I modified it a bit because when I tested your original to find the sum of the number of times each vertex was traversed, I got an incorrect answer. Can someone post a passing solution to Timus 1553 using this implementation? My original test case These are the edges in the tree 0 1, 1 3, 3 4, 3 5, 0 2, 2 6, 2 7Actions the program performedAdd 1 to each value on the path from 4 to 5 Query on the number the path from 4 to 6Using your implementation I got an answer of 5, which is wrong.
•  » » 21 month(s) ago, # ^ |   0 where the code at
•  » » » 21 month(s) ago, # ^ |   0 My apologies. https://ideone.com/p8ntsWThe Segment Tree is from Benq's github.
 » 14 months ago, # |   +3 Extra care must be taken in processPath if the binary operation isn't commutative, you'll need two segment trees, one for downward sums and one for upward sums.
 » 2 months ago, # |   0 Does it also handles the case when u == v? I think it is not. Can anyone help.
 » 2 months ago, # |   0 If a tree is like a straight line(1-> 2-> 3-> 4) like so and all queries are like (1, n) i.e from top to bottom can HLD also compress path to handle these queries?