# Djio and Stone Ocean

For brevity, call the longest subsequence with alternating colors as the **longest interesting** subsequence.

**Observation.** The longest interesting subsequence of a binary sequence can be found by removing consecutive occurrences of $0$s and $1$s. For instance, the longest interesting subsequence of $00011101001$ is $010101$. Therefore, its length is $1$ plus the number of consecutive indices with differing values.

Define the weight of an edge from $u$ to $v$ as $A_u \oplus A_v$. This way, the length of the longest interesting subsequence of the path from $a$ to $b$ is equal to $1$ plus the distance from $a$ to $b$. Consequently, to find $\max_{1 \le y \le N} F(x, y)$, it is enough to find the furthest vertex from $x$.

This can be done using a full Euler tour and a segment tree with lazy propagation. The remainder of this editorial will explain the details of doing so.

Root the tree arbitrarily. Let $T$ be the full Euler tour sequence of the tree. For example, the full Euler tour of the tree in the sample test case is $T = [1, 2, 6, 3, 6, 2, 4, 2, 1, 5, 1]$. Also, define $\mathrm{pos}(i)$ as the index of the first occurrence of $i$ in $T$, and $\mathrm{LCA}(i, j)$ as the lowest common ancestor of vertices $i$ and $j$.

**Lemma 1.** For all vertices $u$ and $v$ such that $\mathrm{pos}(u) \le \mathrm{pos}(v)$, the following two conditions hold in the subarray $[\mathrm{pos}(u)..\mathrm{pos}(v)]$ of $T$. If $l = \mathrm{LCA}(u, v)$, then:

- There exists at least one occurrence of $l$.

- There exists no occurrence of $p$, where $p$ is a proper ancestor of $l$.

**Proof.** Examine the nontrivial case when $l \neq u$ and $l \neq v$. Notice that for a vertex $a$ which is an ancestor of either $u$ or $v$, $a$'s occurrence in the subarray must not be its first or last occurrence; $a$ will only occur when moving across $a$'s children. Because $u$ and $v$ are in different children of $l$, $l$ must occur. Meanwhile, for all $p$ which is a proper ancestor of $l$, $u$ and $v$ are in the same child, which makes $p$ not occur. $\blacksquare$

**Lemma 2.** Let $\mathrm{dist}(u, v)$ be the distance from vertex $u$ to $v$, and $D(u)$ be the distance from vertex $u$ to the root. It is true that $\max_{\mathrm{pos}(u) \le \mathrm{pos}(i)} \mathrm{dist}(u, i) = \max_{\mathrm{pos}(u) \le \mathrm{pos}(a) \le \mathrm{pos}(b)} (D(u) - 2D(a) + D(b))$.

**Proof.** Recall that $\mathrm{dist}(p, q) = D(p) - 2D(\mathrm{LCA}(p, q)) + D(q)$. We will prove that for any $b$, the value of $a$ minimizing $D(u) - 2D(a) + D(b)$ under the conditions above is $\mathrm{LCA}(u, b)$.

Notice that all edge weights are nonnegative. According to Lemma 1, $\mathrm{LCA}(u, b)$ must occur between $\mathrm{pos}(u)$ and $\mathrm{pos}(b)$, and there exist no proper ancestors of it there. Therefore, $\mathrm{LCA}(u, b)$ is the closest vertex to the root in that subarray, and all vertices in that subarray have it as an ancestor. This makes the value of $D(\mathrm{LCA}(u, b))$ minimum in that subarray. $\blacksquare$

Based on the two lemmas above, we can use a segment tree with lazy propagation to efficiently obtain the value of $\max_{\mathrm{pos}(u) \le \mathrm{pos}(a) \le \mathrm{pos}(b)}{(-2D(a) + D(b))}$. Aside from that value, a node $[L, R]$ in the segment tree also needs to maintain $\min_{L \le \mathrm{pos}(i) \le R} D(i)$ and $\max_{L \le \mathrm{pos}(i) \le R} D(i)$.

Updating the values of $D$ can be done by updating all affected vertices (recall that these vertices form a subarray in $T$). Because the degree of each vertex is quite small, we can update each edge one by one.

Time complexity: $O((N + Q_1 X + Q_2) \log N)$, where $Q_i$ is the number of queries of type $i$ and $X = 10$ is the maximum degree of each vertex.