paths
is not a the right way to store the given tree. It work only if the edges are given in certain format : <node closer to 1> <node farther from 1>. But this need not be the case. Consider :
1 2 3 4 0
1 2
3 2
2 4
1 5
Here path[3]
would never be updated and path[2]
would overwritten. Adjacency list is one common way of representing graphs with large number of nodes but lesser number of edges.
I don’t understand how iterating from 1 \to N could map to MEX of corresponding shortest path from 1.
We need to add it back to the set (which represents the excluded values) when we backtrack from the last of its value. To find whether it is the last one or not we check the mentioned condition.
For getting the mex from node 1 to node i , we need all numbers [0- n] except the numbers on the nodes which are along the path from 1 to i .
So when we backtrack from a leaf node then we must reinsert the values that we removed from the set to get the mex along some other path 1 to j .
This was my logic !
Correct me if i am wrong …
My solution using First technique - Maintaining all elements in a set that are not present in current path from 1 to i :
https://www.codechef.com/viewsolution/60524534
My solution using Segment tree Range sum Query + Binary search :
https://www.codechef.com/viewsolution/60524856
Important corner case :
4
0 1 1 2
1 2
2 3
2 4
Answer = 3 and not 2
We need to reinsert only when we do not have any other value of that type in current path.
Consider path 0 \to 2 \to 1 \to 2 in st we will have \{3, 4 \dots\} when we backtrack to 0 \to 2 \to 1 should we add back the 2 ? 2 is not there in st
but still, we must not add it back.
1 Like
Yeah , got you , Thanks @pandey_adm