Блог пользователя dx24816

Heavy Light Decomposition Implementation
Автор dx24816, история, 6 лет назад, По-английски

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

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
6 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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);
→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Corrected: https://ideone.com/avhp8b

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        → Ответить
        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
          ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

          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.

          → Ответить