Hi, Codeforces.
Recently I have been thinking of the following task:
You are given a tree with $$$N$$$ vertices, each vertex $$$v$$$ has a value $$$a_v$$$ written on it, and you have to process following query ONLINE. given two vertices $$$u$$$ and $$$v$$$, you have to output the MEX of the values on the path from $$$u$$$ to $$$v$$$. The values are not necessarily distinct.
constrains: $$$N$$$<=1e5
If anyone can share any ideas, I will be extremely grateful.
Really interesting problem!
Really interesting comment!
Where is the interesting solution ?!
Interesting task!
I think you can use heavy-light decomposition and store segment trees for count of elements and existence of elements. Then use binary search to find the answer. Probably it's like $$$O(\log n \log^2 M)$$$ though (where $$$M$$$ is $$$max(a)$$$).
Thank you ,but Could you explain this in more details pls?
Ok, sorry, upon further thought, that won't work because I can't think of any simple way to merge the existence of elements...
What I had in my mind, is that you can find mex by binary searching upon the element (say $$$i$$$) and then checking if there are exactly $$$i$$$ distinct elements $$$<i$$$. That's why I needed existence, and for existence, I just have to check if there are non-zero occurrences of the element. But I can't merge existences... it's like merging two sets.
Perhaps, if $$$max(a)$$$ is small, we can do it using bitsets?
Nice one!! Excited to see the solution
There's a simple solution if $$$a$$$ is a permutation: simply build HLD and then query for the minimum in all nodes that do not lie on the path. One, but not the only way to do that would be to use lazy propagation and fill the path with $$$\inf$$$, then query for the minimum on the whole tree, then reset the values back to normal ones (store a copy of the segment tree in an array and use lazy flags to roll back the changes).
If the numbers are big I don't think there's a solution since the only way to do this for a regular array heavily relies on the fact that you query segments, you could reduce the problem by flattening the tree but there would be conflicts with LCA not being considered.