Binary Tree Queries

If a vertex $v$ is chosen as the root, every neighbor of $v$ becomes a child of $v$. Therefore, a vertex of degree at least $3$ cannot be chosen as the root of a binary tree.

Since the tree remains binary for every possible root, every vertex has degree at most $2$. A connected tree whose vertices all have degree at most $2$ is a path.

List the vertices in order from one endpoint of this path. Let $P_v$ be the position of vertex $v$. Let $R$ be the position of the current root, and let $P$ be the position of the queried vertex $i$.

Build a Fenwick tree over this path order. Let $S(x)$ denote the number of white vertices among the first $x$ positions.

If $P<R$, the root lies to the right of $i$. The subtree of $i$ is the interval $[1,P]$, and the path from $i$ to the root is $[P,R]$.

$$a=S(P),\qquad b=S(R)-S(P-1)$$

If $P>R$, the root lies to the left of $i$. The subtree of $i$ is the interval $[P,N]$, and the path from $i$ to the root is $[R,P]$.

$$a=S(N)-S(P-1),\qquad b=S(P)-S(R-1)$$

If $P=R$, vertex $i$ is the current root. Its subtree is the entire tree, while the path contains only $i$.

$$a=S(N),\qquad b=C_i$$

A type 1 query only changes the stored root position. A type 2 query adds $1$ or $-1$ at one Fenwick tree position. A type 3 query uses the formulas above.

Finding the path order takes $O(N)$ time. Building the Fenwick tree takes $O(N\log N)$ time. Every query takes $O(\log N)$ time, so the total time complexity is $O((N+Q)\log N)$ and the memory complexity is $O(N)$.

Solution written by GPT5.6