### fsociety00's blog

By fsociety00, history, 6 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.

• +2

 » 6 years ago, # |   0 Auto comment: topic has been updated by fsociety00 (previous revision, new revision, compare).
 » 6 years ago, # | ← Rev. 2 →   +1 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.
•  » » 6 years ago, # ^ |   0 Can you please Elaborate on how to Maintain the Structure. A submission Code would be Extremely Helpful.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 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[0]=max(B.c[0],C.c[0]); //maximum level of a node A.c[1]=max(B.c[1],C.c[1]); //maximum of -2*level of a node (the lca we try to find) A.c[2]=max(B.c[0]+C.c[1],max(B.c[2],C.c[2])); //a partial maximum used to get the final answer A.c[3]=max(B.c[1]+C.c[0],max(B.c[3],C.c[3])); //another partial maximum A.c[4]=max(max(B.c[0]+C.c[3],B.c[2]+C.c[0]),max(B.c[4],C.c[4])); //the maximum distance }