The first two subtasks were solvable by more or less efficient attempts to simulate the process described in the task statement. We will leave further analysis of those solutions as exercises to the reader.

In the third subtask, you were supposed to answer each Query with the longest path in a tree which starts on the given node ~a~. Note that the definition of path length is a bit peculiar, i.e. instead of summing up the edge weights, we are asked to ~xor~ them. Let's denote the distance between nodes ~x~ and ~y~ with ~d(x, y)~. Note that ~d(x, y) = d(1, x) \mathbin{xor} d(1, y)~ holds for each pair of nodes. We can use this property and keep around the distance from the root to each of the nodes while executing the queries. Finding the greatest distance from a given node ~a~ now boils down to finding another value ~d(1, b)~ from the set of remembered values which when ~xor~-ed with ~d(1, a)~ gives a maximal value. This is a well-known problem which can be easily solved using the trie data structure. If you are not familiar with the problem, we suggest you try to find the solution by yourself. If you don't succeed, check out this link.

The solution which scores all points is conceptually very similar to the one described above. The only problem we are having is that, when we traverse the trie, we don't know whether that part of the trie holds any value that is related to a node that is in a subtree of node ~b~. Imagine that we know the values ~discovery~ and ~finish~ for each node which represent the moments when a dfs traversal function enters and leaves that particular node. Suppose that in each trie node we store a set of discovery times of all tree nodes whose distances from the root live in that subtree of our trie. Then we could simply make sure never to enter a trie node that doesn't hold a value related to subtree of node ~b~ while processing the Query. More precisely, we can traverse a node in a trie if its set of discovery times contains a value that is greater or equal to ~discovery[b]~ and less or equal to ~finish[b]~.

Turns out this is relatively easy to achieve. First we will apply all Add queries (offline) and use a single dfs traversal to find ~discovery~ and ~finish~ values for each node. Then we will traverse through all queries once more and perform the algorithm described above. When adding a new element to the trie, we will simply append the corresponding ~discovery~ value to each of the visited trie nodes. Finally, when answering a query we will make sure we don't visit trie nodes that don't contain values related to the subtree of node ~b~.