Jontrona of Liakot

Setter: Tahsin Masrur
Tester and alternate writer: Rafid Bin Mostofa
Techniques: Euler Tour or DFS Time, Persistent Trie

First find the starting time and ending time of all the nodes of tree using a DFS. Consider the array of time, the subarray starting at starting time of node $U$ (denoted by $S_U$ from now on) and ending time of $U$ ($E_U$) represents the subtree rooteed at $U$. So basically, you need to find the $K$-th number among all the numbers in the subarrays $[S_U, S_V-1]$ and $[E_V+1, E_U]$ after XOR-ing them with $Z$. If we had to do this for a single array always, it'd be easy with Trie, a well-known problem. For our problem, we need to maintain persistent trie i.e. keeping a version of trie for each time in the array of DFS time. We can then just consider the four versions relevant to each query and walk down the tries accordingly to find the solution.

Time complexity: O($Qlog_2(10^9)$)
Space complexity: O($Nlog_2(10^9) + Qlog_2(10^9)$)