Inspiration

https://mirror.codeforces.com/problemset/problem/1748/b

Why the Classic Two-Pointer Technique Fails: The classic two-pointer technique relies on a monotonicity property; that is, if an array is diverse then every subarray of it should also be diverse, or if an array is not diverse then none of its subarrays are diverse. However, the diverse property does not behave monotonically, so a straightforward application of the two-pointer method does not work.

Instead, we modify the approach and compute the count in $$$\max(a)$$$ steps. In the $$$m^\text{th}$$$ iteration, we compute the number of diverse subarrays that have exactly $$$m$$$ distinct elements. Notice that if a subarray has exactly $$$m$$$ distinct elements, then in order to be diverse every element in the subarray must appear at most $$$m$$$ times.

Implementation

For each $$$m$$$ from $$$1$$$ to $$$\max(a)$$$:

• For every right endpoint $$$r$$$, calculate two left indices:
• $$$l_1$$$: the smallest index such that the subarray $$$a[l_1:r]$$$ has exactly $$$m-1$$$ distinct elements.
• $$$l_2$$$: the smallest index such that the subarray $$$a[l_2:r]$$$ has exactly $$$m$$$ distinct elements.

These can be computed efficiently with the two-pointer technique in $$$\mathcal{O}(n)$$$ time.

• Subsequently, for every right endpoint $$$r$$$, calculate the smallest left index $$$l_3$$$ such that in the subarray $$$a[l_3:r]$$$ every element appears at most $$$m$$$ times.
  This, too, can be determined using a two-pointer approach in $$$\mathcal{O}(n)$$$ time.

Note that for all $$$l$$$ with $$$l_2 \le l \lt l_1$$$, if $$$l_3 \le l$$$ then the subarray $$$a[l:r]$$$ is diverse.

Thus, the number of valid subarrays ending at $$$r$$$ for this iteration is given by:

The final answer is then:

Time Complexity: $$$\mathcal{O}(n*\max(a))$$$

Code: 310459724

Solution for $$$n = 2k + 2$$$

Let us define two vectors $$$\mathbf{v}$$$ and $$$\mathbf{w}$$$ as follows:

Here, $$$\mathrm{IDT}$$$ denotes the identity element of the operation $$$@$$$. We then define

Operation Count

• Vector $$$\mathbf{v}$$$: Computed in $$$k$$$ operations total (by building partial products successively).
• Vector $$$\mathbf{w}$$$: Computed in $$$k$$$ operations in a similar way.
• Vector $$$\mathbf{b}$$$: Computed in $$$k$$$ operations by computing each $$$b_i$$$.

Hence, the total number of operations is $$$3k$$$.

Extending to the Case $$$n \neq 2k + 2$$$

When $$$n \neq 2k + 2$$$, partition the array $$$\mathbf{a}$$$ into chunks of length $$$k+2$$$. For each chunk, apply the same procedure to compute the corresponding part of $$$\mathbf{b}$$$. Each chunk requires $$$3k$$$ operations, taking a total of

operations.

Code: 310459799

Input and Function Definitions

Input Description

The interactor receives the following parameters: n, k, h, and fnc.

• n and k are defined as in the problem statement (they are identical).
• h is a unique key.
• fnc is the function number.

Constants

• mod = 2³⁰ (i.e., 1,073,741,824).

Function Definitions

The functions are defined for integer inputs x and y.

• f₀(x, y)

• f₁(x, y)

• f₂(x, y)

• f₃(x, y)

• f₄(x, y)

• f₅(x, y)

Note: Here, $$$\oplus$$$ represents the bitwise XOR operation.

Definitions

Let $$$T$$$ be a tree of size $$$n$$$, and let $$$k$$$ be a positive integer. Define a partition of $$$T$$$ as a collection of disjoint subtrees whose union is $$$T$$$. A subtree is called a good tree if its size is at least $$$k$$$. The good value of $$$T$$$ is the maximum number of good trees that can appear in any partition of $$$T$$$.

A subtree $$$X \subseteq T$$$ is called a minimal subtree with respect to $$$k$$$ if $$$|X| \geq k$$$ and every proper subtree $$$Y \subsetneq X$$$ satisfies $$$|Y| \lt k$$$.

Theorem

There exists an optimal partition of $$$T$$$ (i.e., one attaining the good value) that includes every minimal subtree $$$X$$$ as one of its parts.

Proof

Let $$$P^*$$$ be an optimal partition of $$$T$$$, meaning that it contains the maximum possible number of good trees.

Claim: The nodes of $$$X$$$ must be contained in at most one good tree in $$$P^*$$$.

Proof by contradiction: Suppose the nodes of $$$X$$$ are distributed among at least two good trees in $$$P^*$$$. Let $$$T_1$$$ and $$$T_2$$$ be two such good trees, and assume without loss of generality that $$$T_1$$$ contains the top node (or root) of $$$X$$$. Since $$$X$$$ is a minimal subtree, every proper subtree of $$$X$$$ has size strictly less than $$$k$$$. In particular, the intersection $$$X \cap T_2$$$ is a proper subset of $$$X$$$ and thus must have size $$$|X \cap T_2| \lt k$$$. This contradicts the assumption that $$$T_2$$$ is a good tree (i.e., has size at least $$$k$$$). Therefore, $$$X$$$ can be contained in at most one good tree in $$$P^*$$$.

Since at most one good tree in $$$P^*$$$ contains the nodes of $$$X$$$, we can replace this tree with $$$X$$$ itself (along with any necessary adjustments to maintain a partition) without decreasing the number of good trees in $$$P^*$$$. This guarantees that there exists an optimal partition that includes $$$X$$$ as an independent subtree.

Consequently, the greedy strategy of selecting every minimal subtree (with respect to $$$k$$$) to construct a partition finds the good value of $$$T$$$.

Additional Definitions

• A chain in a tree $$$T$$$ is a sequence of nodes $$${v_1, v_2, \dots, v_m}$$$ such that they form a connected path in the tree and for every pair of nodes $$$(v_i, v_j)$$$ in the chain, one is an ancestor of the other in $$$T$$$.

• A chain decomposition of $$$T$$$ is a decomposition of the tree into chains such that each node is in exactly one chain.

• A subchain of a chain $$$X$$$ is a chain $$$Y$$$ such that an ancestor of each node in $$$Y$$$ lies in $$$X$$$.

• An extended tree is the tree formed by a chain and all its subchains.

• A minimal chain is a chain whose extended tree has size $$$\geq k$$$ but all its subchains have extended trees of size $$$ \lt k$$$.

Greedy Algorithm

The greedy algorithm removes minimal subtrees at each step. The root of a minimal subtree lies in the minimal chain. The idea is to maintain the subtree size of each node and find the lowest node (considering the root of the chain to be the highest) in the chain with subtree size $$$\geq k$$$.

1. Find a chain decomposition of the tree.
2. Store the count of descendants in the same chain for each node.
   When the size of an extended tree becomes $$$ \lt k$$$, add its size to its ancestors in the immediate parent chain(the chain which contains the parent of the root of the extended tree) and remove the current chain from consideration.

$$$O(\frac{n}{k})$$$ modify and query operations on a segment tree are needed to find the value for each $$$k$$$, so the total time complexity is $$$O(n\log^2 n)$$$.

Code: 310459944

Firstly, see that for $$$A[j] = k$$$, we must have every integer from $$$1$$$ to $$$k-1$$$ within $$$P[1:j]$$$. So, $$$A[j] \le j+1$$$.

Secondly, since $$$P$$$ is a permutation, $$$A_n = n+1$$$.

Also,

as all integers in $$$P[1:i]$$$ are present in $$$P[1:j]$$$ also.

These conditions are necessary and sufficient for $$$A$$$ to be valid.

Now, see that if $$$A[j] = k_1$$$ and $$$A[j+1] = k_2$$$ for some $$$k_2 \gt k_1$$$, then $$$P[j+1] = k_1$$$. This is because

(otherwise $$$A[j] \ne k_1$$$), and $$$P[i] = k_1$$$ for some $$$i \le j+1$$$ (because $$$A[j+1] \gt k_1$$$). From these two, we get $$$P[j+1] = k_1$$$.

As stated earlier, for $$$A[j] = k$$$, every integer from $$$1$$$ to $$$k-1$$$ must appear in $$$P[1:j]$$$.

Every permutation $$$P$$$ satisfying the above two constraints will have $$$A$$$ as its corresponding prefix MEX array.

To enforce these two while counting the number of permutations $$$P$$$, we use the following method:

• Initialization: Set $$$ans = 1$$$, which keeps track of the possible permutations $$$P$$$.
• Iteration: Iterate from $$$j = n$$$ to $$$j = 2$$$, and maintain a variable $$$rem$$$, which is the number of integers that can be placed at the current position in $$$P$$$.
• If $$$A[j-1] = A[j]$$$, multiply $$$ans$$$ by $$$rem$$$ and decrease $$$rem$$$ by $$$1$$$ to account for the integer we just placed.
• Else if $$$A[j-1] \ne A[j]$$$, then $$$P[j] = A[j-1]$$$, so $$$ans$$$ remains the same, and $$$rem$$$ increases by $$$A[j] - A[j-1] - 1$$$, because now we can place integers from $$$A[j-1]+1$$$ to $$$A[j]-1$$$ anywhere before this $$$j$$$.

Time Complexity: $$$O(n)$$$

Code: 310460072

Let's find the beauty of only the string $$$s$$$.

We firstly observe that the final string would be some subsequence of $$$s$$$, but not all subsequences of $$$s$$$ can be obtained. For example, you cannot obtain $$$AA$$$ from $$$ABA$$$. In fact, the count would be the number of distinct subsequences of $$$s$$$ for which, if the subsequence contains any two consecutive $$$A$$$s, then there are no $$$B$$$s in $$$s$$$ between the two positions corresponding to these $$$A$$$s. Similarly, if the subsequence starts or ends with $$$A$$$, then there should be no $$$B$$$s before or after the position in $$$s$$$ corresponding to this $$$A$$$. Call such a subsequence good. Call a subsequence semi-good if we only relax the constraint that there should be no $$$B$$$s after the position of the last $$$A$$$ when the subsequence ends in $$$A$$$ (so $B$s are allowed after this position).

Let $$$G$$$ denote the set of distinct good subsequences of $$$s$$$. Let $$$T_i$$$ denote the set of distinct semi-good subsequences that can be obtained from the string $$$s[1,i]$$$ (the prefix of $$$s$$$ of length $$$i$$$). Clearly, $$$T_{i-1} \subseteq T_i$$$. Let

Any string $$$t \in G$$$ also belongs to a unique $$$S_i$$$, but not all strings in $$$\bigcup_{i=1}^{n} S_i$$$ are in $$$G$$$. For example, if $$$s$$$ is $$$AAAB$$$, then $$$AAA \in S_3$$$ but $$$AAA \notin G$$$. Moreover, $$$S_i \cap S_j = \emptyset$$$ for $$$i \neq j$$$.

We first try to find

for each $$$i$$$. Consider any string $$$w \in S_i$$$. We try to think what happens when we append an $$$A$$$ or $$$B$$$ to $$$w$$$. Since $$$w \in T_i$$$ and $$$w \notin T_{i-1}$$$, the last character of $$$s[1,i]$$$ must also be the last character of $$$w$$$. So let's take cases on the last character of $$$w$$$.

• Case 1: The last character of $$$w$$$ is $$$B$$$.
• $$$wB \in S_{j_1}$$$ where $$$j_1$$$ is the least index $$$ \gt i$$$ for which $$$s[j_1] = B$$$. So we do

If no such $$$j_1$$$ exists, we skip this step.

• $$$wA \in S_{j_2}$$$ where $$$j_2$$$ is the least index $$$ \gt i$$$ for which $$$s[j_2] = A$$$. So we do

If no such $$$j_2$$$ exists, we skip this step.

• Case 2: The last character of $$$w$$$ is $$$A$$$.
• $$$wB \in S_{j_1}$$$ where $$$j_1$$$ is the least index $$$ \gt i$$$ for which $$$s[j_1] = B$$$. So we do

If no such $$$j_1$$$ exists, we skip this step.

• The case for appending $$$A$$$ is more complex. Firstly, observe that the number of consecutive $$$A$$$s at the end of $$$w$$$ must be the same as the number of consecutive $$$A$$$s at the end of $$$s[1,i]$$$, otherwise $$$w \notin S_i$$$. If $$$s[i+1] = A$$$ then clearly $$$wA \in S_{i+1}$$$. However, if $$$s[i+1]$$$ is $$$B$$$:
  • Suppose $$$w$$$ contains a $$$B$$$, then $$$wA$$$ belongs to $$$S_{j_1}$$$ where $$$j_1$$$ is the least index $$$ \gt i$$$ for which the number of consecutive $$$A$$$s at the end of $$$s[1,j_1]$$$ is greater than the number of consecutive $$$A$$$s at the end of $$$s[1,i]$$$. We skip this step if no such $$$j_1$$$ exists.
  • Suppose $$$w$$$ does not contain any $$$B$$$. This can only happen when $$$w = s[1,i]$$$ (because if $$$s[1,i]$$$ contains a $$$B$$$, then by the nature of the operation, $$$w$$$ must contain a $$$B$$$ too). Thus, $$$wA$$$ can never be an element of any $$$S_j$$$ for $$$j \gt i$$$.

Clearly, the $$$dp$$$ array can be computed in $$$O(n)$$$ space and time. Now, for each $$$S_i$$$, let's consider which strings in it are contained in $$$G$$$.

• If $$$s[i]$$$ is $$$B$$$, then any string in $$$S_i$$$ is also in $$$G$$$. So we update

• If $$$s[i]$$$ is $$$A$$$ and $$$s[1,i]$$$ contains a $$$B$$$ (which means all strings in $$$S_i$$$ contain a $$$B$$$), then we update

only if the number of $$$A$$$s at the end of $$$s[1,i]$$$ is $$$\leq$$$ the number of $$$A$$$s at the end of $$$s$$$. Otherwise, $$$ans$$$ doesn't change. - If $$$s[i]$$$ is $$$A$$$ and $$$s[1,i]$$$ does not contain a $$$B$$$ (which means $$$S_i = {s[1:i]}$$$), then we update

only if $$$s$$$ does not contain an $$$A$$$. Otherwise, $$$ans$$$ doesn't change.

Thus, the problem can be solved in $$$O(n)$$$ time for a single string $$$s$$$.

Now we are asked to find the beauty count for each prefix of $$$s$$$. Observe that the same $$$dp$$$ array can be used for solving each prefix! For the string $$$s[1,i]$$$, we do the following:

• If $$$s[1,i]$$$ contains only $$$A$$$s, then the answer for this prefix is simply $$$i$$$.
• If $$$s[1,i]$$$ ends in a $$$B$$$, then

• If $$$s[1,i]$$$ ends in an $$$A$$$, then

where $$$I$$$ is the set of all $$$j \lt i$$$ for which the number of consecutive $$$A$$$s at the end of $$$s[1,j]$$$ is $$$\leq$$$ the number of consecutive $$$A$$$s at the end of $$$s[1,i]$$$ (note that $$$s[1,j]$$$ can also end in $$$B$$$).

All of this can be efficiently computed as we process the string from left to right using a Fenwick tree.

Thus, the overall time complexity is $$$O(n \log n)$$$.

Code: 310460120

A greedy algorithm for checking whether there exists a subsequence of $$$a$$$ such that $$$a_{i_j} \ge b_j$$$ for all $$$j$$$, is as follows: Initialize $$$i = 1$$$. For $$$j$$$ from $$$1$$$ to $$$|b|$$$, find the first position $$$k \ge i$$$ such that $$$a_k \ge b_j$$$. If no such position exists, the required subsequence does not exist. Otherwise, set $$$i = k + 1$$$ and continue. If the loop terminates, a required subsequence exists.

We can use this greedy algorithm to count the number of valid arrays $$$b$$$. Let $$$dp_{i,x}$$$ denote the number of new valid arrays $$$b$$$ formed, ending at $$$x$$$ if an element $$$\ge x$$$ is found at some position $$$ \gt i$$$ in $$$a$$$. We have

Iterate over $$$i$$$ from $$$1$$$ to $$$n$$$. The number of new valid arrays formed at index $$$i$$$ is

Add $$$s$$$ to answer. For every new valid array formed, we can form another one by appending a value $$$y \geq 1$$$ after finding an element $$$\geq y$$$ in $$$a$$$ after index $$$i$$$. Since the valid arrays corresponding to $$$dp_{i-1, y} (y \leq a_i)$$$ are formed at index $$$i$$$, those $$$dp$$$ values do not carry on to $$$dp_i$$$. So, update the $$$dp$$$ values as follows:

This dynamic programming solution runs in $$$O(n \cdot \max a)$$$ time, but it can be optimized to $$$O(n \log n)$$$ by using a lazy segment tree to store the $$$dp$$$ array for a fixed $$$i$$$. This segment tree supports range set and range sum updates, and range sum queries. The transition from $$$i-1$$$ to $$$i$$$ requires us to obtain the range sum of the $$$dp$$$ array from $$$1$$$ to $$$a_i$$$, set that range to $$$0$$$, and add this sum to the entire $$$dp$$$ array.

Code: 310460238

Suppose we are solving for a prefix of length $$$l$$$. Let $$$S$$$ be the set of indices in the prefix such that the element originally at that position is encountered during the process (i.e. For every element originally at an index in $$$S$$$, there exists some position such that when we move to that position during the process, we find this element at that position and add its value to the cost). Define $$$T$$$ as the complement of $$$S$$$ in this prefix. To reach indices in $$$T$$$ while having an element outside the indices in $$$T$$$ present at those indices, we must swap the element at that index with some element originally outside $$$T$$$ before visiting it; hence, at least $$$|T|$$$ swaps are necessary.

Let $$$m = \min(a_1,a_2,\dots,a_n)$$$ be a minimum element in the array.

Claim: If $$$\geq|T|+1$$$ swaps are made, then it is optimal to perform all swaps involving the minimum element $$$m$$$, and visit all indices in $$$T$$$ with the cost of that element.

Proof: If $$$\geq|T|+1$$$ swaps are made, then the cost of the process is at least $$$\sum_{i\in S} a_i \;+\; (|T|+1)\cdot k \;+\; m\cdot|T|.$$$ We can achieve this cost using the following process:

Let $$$X = T \cup {i_m}$$$, where $$$i_m$$$ is an index with $$$a_{i_m} = m$$$. Iterate from $$$x=0$$$ to $$$l-1$$$. If $$$x+1\in X$$$, swap the current position of $$$m$$$ with $$$x+1$$$. Move to $$$x+1$$$.

Now, we are left with the case with exactly $$$|T|$$$ swaps. For each index in $$$T$$$, we must perform exactly one swap from an element in $$$S$$$ or from the suffix (positions $$$l+1,\dots,n$$$) to it. No other type of swaps are allowed, as then the required number of swaps would exceed $$$|T|$$$. Notice that if an index $$$i$$$ in $$$S$$$ is swapped with an index in $$$T$$$ before position $$$i$$$ is reached in the process, an additional swap would be required later to recover that position (since position $$$i$$$ then holds an element from $$$T$$$ and has not yet been reached). Hence, an index $$$i$$$ in $$$S$$$ can only be swapped to an index $$$j$$$ in $$$T$$$ such that $$$j \gt i$$$ (after position $$$i$$$ has been reached), while indices in the suffix can be swapped to any position in the prefix at any time.

Thus, for this case, the cost of reaching an index $$$x$$$ (i.e. moving from position $$$x-1$$$ to $$$x$$$, where the move normally costs $$$a_x$$$) is

where $$$\operatorname{pref}_{\min}(x)$$$ is the minimum element in the prefix up to $$$x$$$ and $$$\operatorname{suf}_{\min}(l+1)$$$ is the minimum element in the suffix (i.e. positions $$$l+1,\dots,n$$$). The summation of this over $$$x\le l$$$ can be computed for each $$$l$$$ by iterating from $$$l=1$$$ to $$$n$$$, maintaining in a multiset the values of $$$\min\bigl(a_x,\; \operatorname{pref}_{\min}(x)+k\bigr)$$$ that exceed $$$\operatorname{suf}_{\min}(l+1)+k$$$, and their sum, so that we can replace these costs with $$$\operatorname{suf}_{\min}(l+1)+k$$$ to compute the cost for this case.

For the first case (with at least $$$|T|+1$$$ swaps), the total cost can be viewed as covering each element with $$$\min(a_i,\; m+k)$$$ and adding an extra cost of $$$k$$$ for the additional swap.

Code: 310468120

The following pattern works for any $$$n$$$ and $$$k$$$:

Each element from $$$1$$$ to $$$n$$$ occurs twice in the array. Furthermore, for any two occurrences of an element $$$e$$$, there are at least $$$k-1$$$ different elements between them. Thus, no subarray of length $$$k$$$ can contain a repeated element.

Finally, the $$$(k+1)$$$-length subarray

contains the repeated element $$$k$$$.

Time Complexity: $$$O(n)$$$

Code: 310460341

First note that for any two vertices $$$u$$$ and $$$v$$$, to minimise the sum of weights, we will always have to take the path either directly from $$$u$$$ to $$$v$$$ or $$$u$$$ to $$$x$$$ to $$$v$$$, where $$$x$$$ is a point in the unique path from $$$u$$$ to $$$v$$$ in the original tree.

Second, also note that the weight of any edge in the complete graph, that is the range of the function $$$d$$$, is $$${0,1,2,3}$$$.

This is because, let $$$u$$$ and $$$v$$$ be any two vertices. Let the path between the two vertices be $$$u$$$, $$$v_1$$$, $$$v_2$$$, $$$\dots$$$, $$$v$$$. Let $$$a_1$$$, $$$a_2$$$, $$$\dots$$$ be the values assigned to these vertices. If none of the vertices in the path have the value assigned to be $$$0$$$, clearly the $$$\mathrm{MEX}(S)=0$$$ and correspondingly $$$d(u,v)=0$$$. If $$$0$$$ is present, we take two cases.

Say $$$a_i=0$$$. If neither $$$a_{i-1}$$$ nor $$$a_{i+1}$$$ are equal to $$$0$$$, then we can easily divide the path into two parts, say $$$u$$$ to $$$x$$$ to $$$v$$$, such that

That is, one of them is one and the other zero. Hence in this case, $$$d(u,v)=1$$$.

If either of them is $$$1$$$, (without loss of generality, assume $$$a_{i+1}=1$$$), we further divide this into two cases. It can be similarly seen by case analysis that if $$$a_{i-1}=2$$$ then $$$d(u,v)=3$$$ and if $$$a_{i-1} \neq 2$$$, then $$$d(u,v)=2$$$.

Hence, we can see that the value of $$$d(u,v)$$$ for any vertices is determined by the position of vertices with values $$$0$$$, $$$1$$$, and $$$2$$$, whether they are in the path between $$$u$$$ and $$$v$$$ in the tree or not.

In the optimal tree, we want to maximize the occurrences of the pattern $$$2$$$-$$$0$$$-$$$1$$$ in the paths as much as possible. Hence, the values $$$2$$$, $$$0$$$, and $$$1$$$ need to occur in order.

To maximize the required occurrences, we run a DFS and place $$$0$$$ at the current node at every time. Then, to maximize the occurrences, we place $$$1$$$ at the root of the subtree (of the original tree considering the current node as the root) with the highest nodes contained in it, and $$$2$$$ at the root of the subtree with the second highest nodes.

This is because if the sizes of the subtrees with roots assigned $$$1$$$ and $$$2$$$ are $$$a_1$$$ and $$$a_2$$$, respectively, then it can be shown that the answer we can achieve in this setting is:

where the first term represents the case when $$$d(u,v)\ge1$$$, the second term represents the case when $$$d(u,v)\ge2$$$, and the third term represents when $$$d(u,v)\ge3$$$.

Now, we check whether the value that we have achieved with $$$0$$$ at the current node is the maximum we have achieved so far, and if it is so, we update the answer.

Note: If the current node is a leaf node, we would have to handle it separately, as it would have only one subtree.

Time Complexity: $$$O(n\log(n))$$$

Code: 310460432

A naive approach for solving this problem would be to calculate the minimum distance from every node in set $$$S$$$ and every node in set $$$T$$$ to all vertices of the tree using either dynamic programming (DP) or multi-source Dijkstra. Then, we take the minimum sum over all nodes. However, this approach runs in $$$O(n)$$$ per query, which is inefficient for large values of $$$n$$$. We need to optimize this solution.

Let the minimum distance be achieved between some $$$s \in S$$$ and some $$$t \in T$$$. Then, the shortest path between them must pass through their Lowest Common Ancestor (LCA). Thus, the only relevant nodes we need to consider are:

• All nodes in $$$S$$$
• All nodes in $$$T$$$
• All nodes $$$u \in V$$$ such that $$$u = \text{LCA}(s, t)$$$ for some $$$s \in S$$$, $$$t \in T$$$

Enumerating all such LCAs is a common idea in tree problems. We run a Depth First Search (DFS) from any root and sort the vertices of $$$S \cup T$$$ according to their in-times. Let these sorted vertices be $$$v_1, v_2, \dots, v_{|S| + |T|}$$$. We only consider the LCAs of consecutive pairs $$$(v_i, v_{i+1})$$$ for $$$1 \leq i \lt |S| + |T|$$$.

Once we have the complete set of nodes, say $$$X$$$, we need to construct a tree using only these vertices. This structure is called the Virtual Tree of $$$(S \cup T)$$$. A simple way to construct it is as follows:

1. Sort the nodes in $$$X$$$ in order of depth from the root (not by distance).
2. Construct a Range Minimum Query (RMQ) structure on $$$X$$$.
3. Recursively build the virtual tree:
4. Find the node in the range $$$[l, r]$$$ with the minimum depth (say at index $$$\text{idx}$$$).
5. Make this node the root of the virtual tree.
6. Recursively construct the left subtree using the range $$$[l, \text{idx} - 1]$$$ and the right subtree using the range $$$[\text{idx} + 1, r]$$$.

The edge lengths in the Virtual Tree are computed as:

where $$$\text{dist}[i]$$$ denotes the distance of the $$$i^{th}$$$ vertex from the initial DFS root.

Since the Virtual Tree contains only $$$O(|S| + |T|)$$$ vertices, we can efficiently compute the result using our initial approach. The overall time complexity of this optimized approach is:

which is significantly better than the naive $$$O(n)$$$ per query approach.

Code: 310461150