dx24816's blog

Heavy Light Decomposition Implementation
By dx24816, history, 6 years ago, In English

Hello,

I was trying to do the USACO problem Grass Planting (http://www.usaco.org/index.php?page=viewproblem2&cpid=102), but couldn't get my Heavy Light Decomposition to work. Can somebody direct me to a Heavy Light Decomposition implementation without LCA? Also, could someone also show me how to implement Heavy Light Decomposition with both the values on vertices and then with the values on the edges? I tried using Al.Cash's implementation, but for some reason, it failed. Thanks!

Edit: I got the edge version to work on the grass planting problem my messing around with Al.Cash's implementation, but can't vertex version to work. I was trying to do Timus 1553 (http://acm.timus.ru/problem.aspx?space=1&num=1553), but keep getting WA on test case 4. I'm pretty sure it's because of my HLD, and I'm not sure what's going on. Can somebody point out my error?

My code (https://ideone.com/k4gvQX)

-dx24816

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Ok. You should to save some information:
p[v] — parent of v
deep[v] — deep v :)
nst[v] is a number of segment tree containing v
top[nst[v]] — is the number of the vertex from the segment tree[nst[v]] with the least depth.

Algorithm:
0. you should make some on way from A to B

while (nst[a] != nst[b]) {
  if h[nst[a]] < h[nst[b]]
    swap(a, b);
  make_something(nst[a], a, top[nst[v]]);
  a = p[top[nst[v]]];
}
make_something(nst[a], a, b);
→ Reply
»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Corrected: https://ideone.com/avhp8b

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Isn't this the code on your github for edges? I used this code to write the edge version, but I wasn't sure how to modify it to make the vertex version. I'm pretty sure this is the edge version. I might be wrong though, since I'm new to HLD.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      Yes, it is the edge version. You've already seen the vertex version, and I'm pretty sure that works correctly.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Wait, I tried a simple test case, but it failed.

        https://ideone.com/p8ntsW

        I expect the answer to be 2, but it gives 5. I just used your segment tree, and I didn't modify the HLD code at all. I want it to out put the sum of the values on each vertex in the path from 4 to 6, given that we already added 1 to each vertex on the path from 4 to 5.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          ← Rev. 2   Vote: I like it +3 Vote: I do not like it

          This is because the original implementation uses a segment tree which does operations on intervals l ≤ x < r,  while mine does it on l ≤ x ≤ r.

          → Reply