[HELP] Online mex queries

Revision en1, by Hosen_ba, 2023-09-13 15:35:16

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.

Tags trees, mex, range query, help

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Hosen_ba 2023-09-13 15:35:16 470 Initial revision (published)