CHOICE

Use a DFS Euler tour to represent every subtree of a vertex $x$ as an interval $[in_x,out_x]$.

Let $u$ be Woohyeon's current vertex, and maintain $d(v)=\mathrm{dist}(u,v)$ for every vertex $v$. If Woohyeon moves from $u$ to an adjacent vertex along an edge of length , distances to vertices on the side of that edge decrease by , while distances to vertices on the side increase by .

If $x$ is a child of $u$, add $w$ to every distance, then subtract $2w$ from the subtree of $x$. If $x$ is the parent of $$, subtract from every distance, then add to the subtree of .

Build a lazy segment tree whose nodes store two minima: the minimum distance to a selected vertex and the minimum distance to a not-selected vertex. A range addition shifts both minima. A range state flip swaps the two minima. Both updates can be performed by lazy propagation. For a type-$3$ query, read the minimum for selected vertices at the segment-tree root, or return $-1$ if none exists.

Preprocessing takes $O(N)$ time. Every query takes $O(\log N)$ time, with $O(N)$ memory. Use 64-bit integers for distances and updates.