Here is the video editorial for the problem FCTRE
Prerequisites
PS : Sorry for making video too long , I didn’t wanted to but couldn’t help.
again the same post?
yeah because codechef has deleted my previous post for I do not know what reason
I tried doing this with the Naive approach of your video on LCA, but getting a WA on SubTask 1. Can you help me out figuring out what is wrong?
https://www.codechef.com/viewsolution/31525318
First I precomputed the Sieve, and added factors and their powers for each weight. Then kept adding factors and powers as I moved from u v to their lca
first thing you are doing wrong is you are swapping u and v based on the nodes values , but you have to swap u and v based on their level in tree (as explained in the video)
Thanks man, that did it. That was the only problem…
I dont know if it is okay to ask here, but I tried this question many times and had written my solution ( CodeChef: Practical coding for everyone )on the idea of Mo’s algorithm, flattening of tree (tour on tree) but after several attempts I wasn’t able to crack TLE on last few cases. Can somebody help what mistake I might be commiting. Please help.
Thanks in Advance 
change you comparator function
bool operator < (const query& rhs){
return (BL[l] == BL[rhs.l]) ? (r < rhs.r) : (BL[l] < BL[rhs.l]);
}
read this comment by “Arpa” about optimization
Massive upgrade, initially it was all tle except one of final test case, now it is all passed except one. Thanks man, that was superawesome, great. Only One left CodeChef: Practical coding for everyone
I have to try to optimise something else as well. Let me try that and will let you know.
Thanks a lot again
Thanks @waqar_ahmad224 Now fully Accepted.
https://www.codechef.com/viewsolution/31888586
If you don’t mind I have one more question, how that comparator had such great effect and how did you get to know about that
Well i was as fed up as you were because of that TLE , i tried so many optimizations myself but couldn’t go through the last test case , after almost giving up I thought to ask on codeforces about optimization techniques for Mo’s.
Then before asking i thought to do a google search(should have done it earlier) and found 2 articles explaining optimization on Mo’s.
one of them is what I have sent you
oh nice, I didn’t even thought of that ,such optimization could ever exist.
That’s why we have a lot to learn
Hey bro cn u help in resolving the runtime error while storing the dfs-order in the array.While I need to find the LCA for the 2 nodes I tried to store the dfs-order in an array but it is giving array index out of range.
This is the link to my code in which I just scanned the inputs…and stored the dfs-order in an array.But this code is getting runtime error due to array out of index range when I submit it in Factor Tree question…I have removed rest of code and have only given the code which causes runtime error.Please help I am stuck from 2 weeks in removing this runtime error.When I try with my test cases it works fine.but when I try to submit it in Factor Tree question it shown runtime error.
I used the DFS-order to calculate the LCA for the 2 nodes.But this is not much of use for now as I have removed all the rest of code and just eft a code which scan all the inputs and just make the dfs-order.
when you are debugging something , try using print statements (best debugging tool for beginners).
The problem is you are not initializing index variable to be 0 in every test case.
you’re always welcome man
Why did u use block size = 1200 ,shoudn’t it be equal to sqrt(2*n) because tree flattening array size gets twice?
I was doing some experiment , yes you can take that size too
Can you explain more about it because if we are using block size of sqrt(2*n) then though it is passing but max time is 7.11 and with bock size of 1200 max time is 5.34 i think that a huge difference!!!