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 UU (denoted by SUS_U from now on) and ending time of UU (EUE_U) represents the subtree rooteed at UU. So basically, you need to find the KK-th number among all the numbers in the subarrays [SU,SV1][S_U, S_V-1] and [EV+1,EU][E_V+1, E_U] after XOR-ing them with ZZ. 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(Qlog2(109)Qlog_2(10^9))
Space complexity: O(Nlog2(109)+Qlog2(109)Nlog_2(10^9) + Qlog_2(10^9))



91% Solution Ratio
tmwilliamlin168Earliest, Jan '20
user.2599Fastest, 0.9s
mumith_fahim99Lightest, 49 MB
Kuddus.6068Shortest, 1233B
Toph uses cookies. By continuing you agree to our Cookie Policy.