Statement

You are given a tree with N nodes, numbered from 1 to N. The edges are numbered from 1 to N-1 and edge i has a weight w_i. The difference of two nodes u and v is the bitwise XOR of the edge weights on the simple path between u and v. Formally, if the simple path between u and v consists of edges e_1, e_2, …, e_k, then the difference of u and v is w_e_1 \oplus w_e_2 \oplus … \oplus w_e_k. Let I be the set of interesting nodes (I is initially empty). Q operations are performed on this set: in one operation, a node is either added to or removed from I. After each operation, you have to find the maximum difference between two distinct interesting nodes.