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.