How to solve SPOJ QTREE with centroid decomposition?

It’s quite easy with HLD but I have no idea how to implement it so I went with centroid decomposition. Handling the max queries is relatively simple but I have no idea on how to to update. My idea is to make an array A[LN][N] where A[i][j] stores the max weight edge from centroid at ith level to j. Let X be the LCA of given nodes a and b, then the answer to a query is simply max(A[level(X)][a], A[level(X)][b]). But how to handle the update queries? Is it possible with centroid decomposition at all?

Problem Link: http://www.spoj.com/problems/QTREE/

Some discusssion: http://codeforces.com/blog/entry/19542 (Although he says there “might” be a solution. I wanna know if there really is.)

Keep a multiset of all the edge weights on the path from i to j in A[i][j]. Each node has log N ancestors, so it will be added log N times, so building complexity is N log^2 N and update complexity is log^2 N. Query is just taking the max element of the two multisets you get in the query.

Is there any proper tutorial of this type of application of centroid decomposition available.
I guess problems QTREE and QTREE3 both require the same type of application.

1 Like

Mate,
I too wanna learn both HLD as well as centroid decomposition, would be great if u shared ur HLD implementation…

Thanks

Read carefully, I said I have no idea how to implement HLD, I implemented Centroid decomposition instead. :stuck_out_tongue:

Mate
If u have solved that problem in any way (HLD, centroid decomposition, any other algorithm) please share the link…

I have been looking for both these decompositions for days…


here you go, an explained implementation of centroid decomposition to handle only the queries of QTREE, that is finding the max weight edge between any two given nodes. I commented it and even gave an example test to test it. :slight_smile:

Thanks mate…

Can anyone help me with QTREE4 problem
Link: