How to solve SPOJ QTREE with centroid decomposition?

help
, ,
1

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: Centroid Decompostition in QTREE - Codeforces (Although he says there “might” be a solution. I wanna know if there really is.)

2

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

Thanks

3

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

4

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…

5


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:

6

Thanks mate…

7

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.

8

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