Khalell's blog

Find Mex in a tree path
By Khalell, history, 9 months ago, In English

i have a problem as follow Given a tree with n nodes with unique value for each node and q queries as given two nodes a and b ,find Mex in the path from a to b for each query

(1<n,q<200000)

my solution is using Mo algorithm as mentioned Here. i can find the Mex either using segment tree or set with log(n) for each query,but i think it is a bit hard for my solution to be valid under this constraints .

is there another solution with a better time complexity ?

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Khalell (previous revision, new revision, compare).

→ Reply
»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Because of unique value for each node, I think you can for each k find the shotest path p[k] such that 0...k is all on the path p[k]. Then binary search for each query. Can be done with O((n+q) log n).

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.net/blog/entry/100910

I hope this will help you a bit!

→ Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

Have a look at CF 1930 H

The solution($$$O(n \cdot \log(n))$$$) to 1930 H would work even if you had updates in your problem.

→ Reply