Minimum xor over tree

Can someone help me with this?

1 Like

Just flatten the tree using dfs. After that you know the in time and outtime of every node’s subtree. Make a persistent trie on the flattened array, and find the number that gives you max xor with k in the subtree of given node. since the values of numbers are pretty small, we can make a segtree for each value that occurs in the array. apply rmq on the segtree of found value. Here is my submission : https://www.codechef.com/viewsolution/23932063

1 Like