Practice Maximum Genetic Difference Query

The parents array describes a rooted tree with nodes numbered 0 through n-1. A node's genetic value is its own number; the root has parent -1. For each query [node,value], choose node itself or one of its ancestors and maximize value XOR the chosen node number. Return the maximum for every query in its original order. Nodes on other branches are not eligible. Approach: Group queries by node. Traverse the tree while maintaining a counted binary trie containing exactly the current root-to-node path. Insert a node before answering its queries and remove it when leaving. For each value, prefer the opposite bit at each trie level whenever an active entry exists there. This gives O((n+q) log U) time, where U bounds the integer values. An iterative traversal avoids overflowing the call stack on a long chain. Worked example: The ancestors eligible for query [3,1] below are 3,2,0. Their XOR results are 2,3,1, so the answer is 3.