Two Subtrees
Contest: Educational Codeforces Round 140 (Rated for Div. 2)
Difficulty rating: 3100
Tags: data structures, trees

You are given a rooted tree consisting of $$$n$$$ vertices. The vertex $$$1$$$ is the root. Each vertex has an integer written on it; this integer is $$$val_i$$$ for the vertex $$$i$$$.

You are given $$$q$$$ queries to the tree. The $$$i$$$-th query is represented by two vertices, $$$u_i$$$ and $$$v_i$$$. To answer the query, consider all vertices $$$w$$$ that lie in the subtree of $$$u_i$$$ or $$$v_i$$$ (if a vertex is in both subtrees, it is counted twice). For all vertices in these two subtrees, list all integers written on them, and find the integer with the maximum number of occurrences. If there are multiple integers with maximum number of occurrences, the minimum among them is the answer.

Input format:
The first line contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of vertices in the tree.

The second line contains $$$n$$$ integers $$$val_1, val_2, \dots, val_n$$$ ($$$1 \le val_i \le 2 \cdot 10^5$$$) — the numbers written on the vertices.

Then $$$n - 1$$$ lines follow, each containing two integers $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le n$$$) representing an edge between vertices $$$x$$$ and $$$y$$$. These edges form a tree.

The next line contains one integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — the number of queries to process.

Then $$$q$$$ lines follow. The $$$i$$$-th of them containing two numbers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$) — the roots of subtrees in the $$$i$$$-th query.

Output format:
For each query, print one integer — the number that has the maximum amount of occurrences in the corresponding pair of subtrees (if there are multiple such numbers, print the minimum one among them).

Constraints:
Time limit: 9.0 s
Memory limit: 1024.0 MB

Note:
In the $$$1$$$-st query, the pair of subtrees consists of vertices $$$[2, 4, 7, 8]$$$, and the numbers written on them are $$$\{1, 2, 2, 4\}$$$. The number $$$2$$$ occurs twice, all other numbers — at most once, so the answer is $$$2$$$.

In the $$$2$$$-nd query, the pair of subtrees consists of vertices $$$[3, 5, 6, 7, 7, 8, 8]$$$, and the numbers written on them are $$$\{3, 3, 3, 2, 2, 4, 4\}$$$. The number $$$3$$$ has the maximum number of occurrences.

In the $$$4$$$-th query, the pair of subtrees consists of vertices $$$[1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8]$$$, and the numbers written on them are $$$\{2, 2, 1, 1, 3, 3, 2, 2, 3, 3, 3, 3, 2, 2, 4, 4\}$$$. The numbers $$$2$$$ and $$$3$$$ are the most common, the minimum of them is $$$2$$$.

Example input:
8
2 1 3 2 3 3 2 4
1 2
1 3
2 4
3 5
3 6
3 7
7 8
6
2 7
3 7
2 3
1 1
5 6
1 3

Example output:
2
3
3
2
3
3

Editorial:
Original solution (by shnirelman)
First, let's solve the following problem: we need to maintain a multiset of numbers and process queries of $$$3$$$-th types: add a number to the multiset, remove one occurrence of a number from the multiset (it is guaranteed that it exists), calculate the mode on this multiset. To do this, we will maintain the array $$$cnt_i$$$ — the frequency of $$$i$$$ in the multiset. Now the mode is the position of the leftmost maximum in this array. There are many ways to search for this position, we will use the following: we will build a sqrt-decomposition on the array $$$cnt$$$: for a block we will maintain a maximum on this block and an array $$$c_i$$$ — the number of positions $$$j$$$ in this block, such that $$$cnt_j = i$$$. Since in each of the initial requests $$$cnt_i$$$ changes by no more than $$$1$$$, the maximum in the block also changes by no more than 1 and, using the $$$c$$$ array, it is easy to update it after each query. Now, to find the mode (the position of the leftmost maximum in the $$$cnt$$$ array), you first need to go through all the blocks to find the value of the maximum and the leftmost block in which this maximum occurs, then iterate over the desired position in this block. Thus, queries to add and remove an element run in $$$O(1)$$$, and a mode search query runs in $$$O(\sqrt{A})$$$, where $$$A$$$ is the number of possible distinct values, in a given problem $$$A = 2 \cdot 10 ^ 5$$$.
Now let's get back to the problem itself. Let's build a Preorder traversal of our tree. Let $$$tin_v$$$ be the position in the $$$0$$$-indexing of the vertex $$$v$$$ in the Preorder traversal, $$$tout_v$$$ be the size of the Preorder traversal after leaving the vertex $$$v$$$. Then the half-interval $$$[tin_v, tout_v)$$$ of the Preorder traversal represents the set of vertices of the subtree of the vertex $$$v$$$. For the $$$i$$$-th query, we will consider $$$tin_{v_i} \le tin_{u_i}$$$.
Let $$$sz_v = tout_v - tin_v$$$ be the size of the subtree of $$$v$$$, $$$B$$$ be some integer, then $$$v$$$ will be called light if $$$sz_v < B$$$, and heavy otherwise. A query $$$i$$$ is called light (heavy) if $$$v_i$$$ is a light (heavy) vertex. We will solve the problem for light and heavy queries independently.
Light queries. Let's use the small-to-large technique and maintain the multiset described at the beginning of the solution. Let at the moment we have this multiset for the vertex $$$w$$$. Let's answer all light queries for which $$$u_i = w$$$. To do this, take all the vertices from the subtree of $$$v_i$$$ and add the numbers written on them, calculate the mode on the current multiset — this will be the answer to the query, and then delete the newly added vertices. In the standard implementation of small-to-large, you need to maintain several structures at the same time, which in this case is impossible due to the fact that each of them takes up $$$O(A\sqrt{A})$$$ of memory. This problem can be avoided, for example, as follows: before constructing the Preorder traversal for each vertex $$$v$$$, put its heaviest son at the head of the adjacency list. Then it will be possible to iterate over the vertices in the order of the Preorder traversal, preserving the asymptotics. This part of the solution runs in $$$O(n\log{n} + qB + q\sqrt{A})$$$.
Heavy queries. Let's divide all heavy vertices into non-intersecting vertical paths, so that two vertices from the same path have subtrees that differ by no more than $$$B$$$ vertices, and the number of the paths themselves is $$$O(\frac{n}{B})$$$. To do this, let's take the deepest of the unused heavy vertices and build one of the desired paths, going up to the parent, while the first of these conditions is met. Then we mark all the vertices in this path as used, and start over. We will continue to do this while there are still unused heavy vertices. It is easy to see that the resulting paths are vertical and the subtrees of two vertices from the same path differ by no more than $$$B$$$ by construction. Let's prove that there are not very many of these paths. To do this, we will understand in which cases the path breaks:
1. If the current path contains a root, then since the root has no parent, the path will terminate. Obviously, this path is only $$$1$$$.
2. If the parent of the last vertex of the path has only one heavy child (this last vertex itself). From the construction, a break means that the number of vertices in this path plus the number of children outside the heaviest son subtree of the parent of the last vertex and each vertex of the path, except for the initial one, is more than $$$B$$$ in total, but each of the counted vertices can be counted in only one of such cases, that is, the number of paths that terminate in this way does not exceed $$$\frac{n}{B}$$$.
3. If the parent of the last node has more than one heavy child. Let's leave only heavy vertices in the tree (since the parent of a heavy vertex is a heavy vertex too, it will indeed be a tree (or an empty graph)). This tree contains at most $$$\frac{n}{B}$$$ leafs. Calculating the total degree of the vertices of this tree, we can see that there are at most $$$\frac{n}{B}$$$ additional sons (all sons of a vertex except one). This means that the number of paths terminating in this way is at most $$$\frac{n}{B}$$$.
Let's divide the heavy queries according to the paths where the $$$v_i$$$ is situated. We will answer queries with vertices $$$v$$$ from the same path together. We will do it similarly to the case with light queries, with minor differences: at the very beginning, we add to the multiset all the vertices of the subtree of the initial vertex of the path and mentally remove these vertices from the subtrees of $$$v_i$$$ vertices. Everything else is preserved. Let's calculate how long it takes: add all vertices from one subtree: $$$O(n)$$$, small-to-large: $$$O(n\log{n})$$$, to answer one query due to condition on vertices from one path we have to add at most $$$B$$$ vertices. Since there are only $$$O(\frac{n}{B})$$$ paths, the whole solution will take $$$O(\frac{n^2\log{n}}{B} + qB + q\sqrt{A })$$$. We take $$$B = \sqrt{\frac{n^2\log{n}}{q}}$$$ and, counting $$$n \approx q$$$, we get $$$B = \sqrt{n\log{n}}$$$ and total running time $$$O(n\sqrt{n\log{n}} + n\sqrt{A})$$$.
Implementation details. As already mentioned, a subtree corresponds to a segment of the Preorder traversal, so $$$2$$$ subtrees are $$$2$$$ segments. We will maintain the data structure described at the beginning on the sum of $$$2$$$ segments. By moving the boundaries of these segments, you can move from one query to another, as in Mo's algorithm. It remains only to sort the queries. Heavy queries are sorted first by path number of $$$v_i$$$, then by $$$tin_{u_i}$$$. Light queries are sorted only by $$$tin_{u_i}$$$, but here you can't just move the segment of the $$$v$$$ subtree, you need to rebuild it for each query.
Bonus. Solve this problem for two subtrees and a path connecting the roots of these subtrees.
Alternative solution (by BledDest)
This solution partially intersects with the one described by the problem author. We will use the same data structure for maintaining the mode; and we will also use DFS order of the tree (but before constructing it, we will reorder the children of each vertex so that the heaviest child is the first one).
Let $$$tin_v$$$ be the moment we enter the vertex $$$v$$$ in DFS, and $$$tout_v$$$ be the moment we leave the vertex. As usual, the segment $$$[tin_v, tout_v]$$$ represents the subtree of vertex $$$v$$$, and we can change the state of the structure from the subtree of the vertex $$$x$$$ to the subtree of the vertex $$$y$$$ in $$$|tin_x - tin_y| + |tout_x + tout_y|$$$ operations. Let this number of operations be $$$cost(x,y)$$$.
Let $$$v_1, v_2, \dots, v_n$$$ be the DFS order of the tree. We can prove that $$$cost(v_1, v_2) + cost(v_2, v_3) + \dots + cost(v_{n-1}, v_n)$$$ is estimated as $$$O(n \log n)$$$ if we order the children of each vertex in such a way that the first of them is the heaviest one.
Proof. Let's analyze how many times some vertex $$$v$$$ is added when we go in DFS order and maintain the current set of vertices. When some vertex is added to the current subtree, this means that the previous vertex in DFS order was not an ancestor of the current vertex, so the current vertex is not the first son of its parent. So, the size of the subtree of the parent is at least 2x the size of the current vertex. Since the path from $$$v$$$ to root can have at most $$$O(\log n)$$$ such vertices, then the vertex $$$v$$$ is added at most $$$O(\log n)$$$ times.
Okay, how do we use it to process queries efficiently? Let's say that the vertex $$$v_i$$$ (the $$$i$$$-th vertex in DFS order) has coordinate equal to $$$cost(v_1, v_2) + cost(v_2, v_3) + \dots + cost(v_{i-1}, v_i)$$$. Let this coordinate be $$$c_{v_i}$$$. Then, if we have the data structure for the query $$$(x_1, y_1)$$$ and we want to change it so it meets the query $$$(x_2, y_2)$$$, we can do it in at most $$$|c_{x_1} - c_{x_2}| + |c_{y_1} - c_{y_2}|$$$ operations, which can be treated as the Manhattan distance between points $$$(c_{x_1}, c_{y_1})$$$ and $$$(c_{x_2}, c_{y_2})$$$.
Do you see where this is going? We can map each query $$$(x, y)$$$ to the point $$$(c_x, c_y)$$$, and then order them in such a way that the total distance we need to travel between them is not too large. We can use Mo's algorithm to do this. Since the coordinates are up to $$$O(n \log n)$$$, but there are only $$$q$$$ points, some alternative sorting orders for Mo (like the one that uses Hilbert's curve) may work better than the usual one.