### fsociety00's blog

By fsociety00, history, 5 years ago, Need help! I tried to solve SPOJ QTREE4. I used centroid decomposition, but still getting TLE (time limit exceeded). In my code, a query is processed in O(log(n)^2). How can I improve complexity? Any suggestions. Here is my code.  Comments (4)
 » Auto comment: topic has been updated by fsociety00 (previous revision, new revision, compare).
 » 5 years ago, # | ← Rev. 2 →   You may try a segment tree on the euler tour.You need to understand the euler tour/rmq algorithm for lca first (it can be found here https://en.wikipedia.org/wiki/Lowest_common_ancestor ).Then,build a segment tree holding the maximum value of lev[node1]-2*lev[node2]+lev[node3] where node1 and node3 are at first occurrence,both are white and node2 can be found between them(and is not neccesarily white)- lev[x] denotes the level of node x.Of course,you need to maintain some helping values (e.g maximum of lev[node1]-2*lev[node2]) but I find this a good segment tree exercise.Finally, you get O(logn) per update.
•  » » Can you please Elaborate on how to Maintain the Structure. A submission Code would be Extremely Helpful.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   This function 'merges' 2 segment nodes(you now the answers for [a;b] in B,for[b+1;c] in C and you get them for [a,c] in A.I'm sorry it isn't very explicit, but i'll try to explain which is every part of the structure.The rest of the segment tree and building euler tour is more of a prequisite and I would PM if requested, but I find the most important part here. Codevoid merg(node &A,node B,node C) { A.c=max(B.c,C.c); //maximum level of a node A.c=max(B.c,C.c); //maximum of -2*level of a node (the lca we try to find) A.c=max(B.c+C.c,max(B.c,C.c)); //a partial maximum used to get the final answer A.c=max(B.c+C.c,max(B.c,C.c)); //another partial maximum A.c=max(max(B.c+C.c,B.c+C.c),max(B.c,C.c)); //the maximum distance }