david89's blog

LCA problem
By david89, 13 years ago, In English

Hi everybody,


I am trying to learn how to solve problems about LCA. I tried to solve this problem http://www.spoj.pl/problems/QTREE/. But, I had some problems implementing the update (CHANGE) operation.

I used the <O(N), O(sqrt(N))> strategy from here http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor. I use an extra array C, where C[node] contains the minimum cost edge on the path from node to p[node], which can be constructed in linear time.

C[node] = 0 if node is in section 0.
C[node] = cost from father of node to node, if the level of node corresponds to the beginning of a section.
C[node] = min(C[father of node], cost from father of node to node).

This array allows to calculate the result of each query in sqrt(n).

If I want to update the cost of an edge a->b, I recalculate the cost of b and all the successors of b in the same section. But this takes too much time.

I can't figure out a better solution for this problem, can you help me?

Thanks in advance.
  • Vote: I like it
  • 0
  • Vote: I do not like it

13 years ago, # |
← Rev. 14   Vote: I like it +3 Vote: I do not like it

Read about Heavy-Light Decomposition

→ Reply
  • 13 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Thank you very much Jokser. I will try to implement a solution using Heavy-Light Decomposition.

    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
There are many ways, how to do it. I did it with HLD, that is O ( N log^2 N ), also there is one another way with same compxity. Using 2d data structures + lca. First you do DFS and for each node you find finish and discovery time. You can see that as 2d point in space. Than you can do 2d sweep from lca to the 2 nodes. Complexity should also be N log^2 N.
→ Reply