Ah that’s nice. I tried implementing this in contest but I wasn’t able to figure out how to deal with nodes appearing twice in the euler tour path… I couldn’t simply multiply them and divide since a_i <= 1e9 and MOD was non prime.
1 Like
Hi
If we just do the naive approach but cache all the products we come across then the time complexity should be N*root(N), right?
For example:
if from root to n1 and n2 we have: (xi,yi,ui,vi)
xi, yi-> ith elements from root to n1 and n2 respectively
ui,vi → weight of xi and yi respectively
eg:
(1,1, 10, 10) (2,2, 11, 11) (3,3, 12, 12) (4,5, 13, 14) (10,11, 15, 16)
now when we calculate scalar product we know that for (ni,nj) = wiwj + (ni-1,nj-1)
this was we store all values on this path in map
i think at max this would result in Nroot(N) complexity
but my code gets TLE
would be great if someone could help me understand why this logic wouldn’t pass
https://www.codechef.com/viewsolution/39532886
3 Likes
You should try unordered_map with a good hash function.
2 Likes
I stored those numbers which are in dot product in a vector and then subtracted old value and added new value after removing the element. Since we cannot do mod inverse.
Can someone please explain what was the difference between subtask 2 and 3 ? why having 10^5 nodes and queries is easier than 3*10^5 ? and how were people able to get AC for subtask 2 but not 3 if there isn’t a huge difference.
2 Likes
this is not the problem being discussed in this thread
If you have already sort the queries by depth then why are storing the result till the root. It’s useless just store for current (u, v) pair.
I tried sorting by height of nodes and then implementing with an unordered map. Only 1 case TLE.
https://www.codechef.com/viewsolution/39631266
What could I have optimized more?
@dtu_amritkumar my solution is a bit similar to yours, except im using recursion. my hash function is from gfg. What is up with case 17.
Try this hash function maybe it will work.
struct pair_hash
{
template <class T1, class T2>
size_t operator()(const pair<T1, T2> &p) const
{
size_t h = (size_t(p.first) << 32) + size_t(p.second);
h *= 1231231557ull;
h ^= (h >> 32);
return h;
}
};
Source: Quora
1 Like
Can anyone provide me a good source/video to learn square root decomposition on trees?
It is possible that if I don’t store all the pairs till root, it might take n^2
eg:
tree->
1 -> 2
1-> 3
2->4
3-> 5
4 -> 6
5->7
and so on
edge between n->2+n for all n>1
in this case if queries are
n-2, n
n-4,n-2
and so on
i will get TLE then because everytime i have to traverse the path and hence n^2
1 Like
Try CodeNCode
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.