Nah still that one case is TLE.
I did same approach but why it giving tle for one subtask where for other subtask it run in less then .57 sec😥
my code link:CodeChef: Practical coding for everyone
My approach was similar to yours but at last I was not able to implement the final steps. I want a bit detailed explanation especially for the last part after sorting the queries.
Thanks in advance bro 
1 Like
I follow his videos. But I didn’t found square root decomposition on trees.
n and n - 2 will be at different height.
yes sorry
i miswrote, should be n, n+1
1
2. 3
4. 5
6. 7
8. 9
something like this
we get queries like
8,9
6,7
and so on
we need to store all pairs till root
I also used the naive approach ,storing the product for all the node pairs that i come across while traversing from given u and v till the root .
This is my solution-
https://www.codechef.com/viewsolution/39616803
I stored the dot product of u and v in a map with the key being 3e5*u +v.
Getting tle in 4 cases ,could anyone help me understand why this logic would not pass.
1 Like
I used BFS to compute parents of each and every node then used DSU like meothed to solve and then later on optimised it using DP,but then too 2 Testcases of last subtask did’nt
pass,can someone help.
code link->CodeChef: Practical coding for everyone
thanks in advance:)
Can you please help me out CodeChef: Practical coding for everyone I have used Mo’s algorithm.For traversing between two points in euler array I made a new array level1 which is initialized to 1 and then while traversing if a node appears once then level1[level[node]] is multiplied by weight of node and if it occurs twice then it is divided.I have stored the changes in res variable.Please help me out as I am getting correct ans for many test cases which I made but not able to find the mistake.
FEMA2 Iron Magnet Wall Solution :- Codechef Nov Challenge Iron Magnet Wall FEMA2 full solution. - YouTube
You cannot divide after using modulo.
1 Like
CodeChef: Practical coding for everyone Why is this TLE? I’m sorting the queries by depth and then caching the results in unorderd_map. I don’t see how the complexity can go beyond O(N+QsqrtN) @l_returns @dtu_amritkumar
1 Like
true
i have done the same and getting TLE 
A bit dumb question but Why you are using map instead of array ? map.find() has a time complexity of O(n). Space would be a problem ?
The problem is to cache the pair <u, v> although both u, v are < 1e5, you can’t use arrays to cache it. You’d have to create an array of size 1e5 x 1e5
I’ve the same doubt. can anyone help?
this is my solution
travelling using parent and storing all in hash. maximum complexity is O(N*root(N))
https://www.codechef.com/viewsolution/39511391
3 Likes
For the second subtask, we can precompute the answer for all pairs for levels having less than \sqrt{N} nodes. So, the number of pairs in a level will be K^2 where K is the number of nodes in the level. So, the total number of pairs will be \sum K^2 and since K\le \sqrt{N} and \sum K=N, in the worst case, there will be N\sqrt{N} pairs when there are \sqrt{N} levels and each level containing \sqrt{N} nodes. Also, now each query can be answered in O(\sqrt{N}) by moving up until we find a level whose answer has been computed. Note that we will move a level up only when it has more than \sqrt{N} nodes and there can be at max \sqrt{N} such levels. Now, the space complexity for this solution is O(N\sqrt{N}) which will work for subtask 2 but is quite high for subtask 3 since N\sqrt{N} can be upto 1.5\times 10^8 when N is 3\times 10^8. And it does fail at Test 15.
1 Like
You are right. It will be O((N+Q)*\sqrt{N}) but you are also using unordered map.
The complexity of unordered_map is O(1) but the constant is high. As in O(10) = O(1) but O(10) will take 10 times more time.
Hence it is not passing. Mine is also with same complexity but without map and hence it is passing.
@bennyjoseph @pankaj0017 @tanmaydatta
5 Likes