The subtask where ~n \le 1000~ could be solved by constructing the whole tree, and then for each query we can find the lowest common ancestor of the given nodes.

Similarly, we can solve the subtask in which there is only one query. The only thing is that we cannot build the whole tree, but rather move towards the root from the given nodes until we reach the same node.

Below we will describe both the offline and online solution. The offline solution is worth 50 points, while for more we need to answer queries in an online fashion. The offline solution means we can load all queries first and respond to them in the order that suits us, while the online solution requires that each query is answered immediately after loading it.

For the offline solution, we will go from the bottom level to the topmost and maintain sets of queries in the subtrees. Note that when we move from one level to another, only one pair of sets merges. We can support this by merging the smaller set into the larger one. The first time some query appears twice in a set, the node represented by that set is the answer for the query, and we can remove the query from consideration.

For the online solution, we first need to build some data structure to help us with answering queries. The idea is to build a reduced tree. Nodes of the tree will be the components of the nodes of the original tree, obtained by removing the edges between the node ~a_i~ and its two children for each ~i~, and an edge will exist between some two nodes if there is an edge between the corresponding components in the original tree.

The tree parametrized by ~a = (1, 2, 6)~, with the components marked.

For each query, it is enough to find the components of the given nodes, and then the solution is the minimum of: the label of the first node from the query, the label of the second node from the query, and the label of the bottom of the component that is the lowest common ancestor of the components from the query on the reduced tree.

Two more implementation details are left: how to build the reduced tree, and how to find components of nodes online. Both issues can be solved with a persistent segment tree.

As in the offline solution, we will go from the bottom level to the top, and each level will have "its own" segment tree (thus we actually need persistence). In the leaves of the segment tree, we keep which component currently represents that node. When we go from one level to another, we connect the two components as follows: replace the left component with the label of the new component, and replace the right component by zero, which means there is no component there anymore. We connect the new component with the left and the right components with an edge in the reduced tree.

Note that now by supporting the query "give me the ~k^\text{th}~ leaf that has value greater than zero", we can easily find out in which components the nodes from the query are located.