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.)