P4116 Qtree3

Given a tree with $N$ nodes ($N-1$ edges). Each node is either white or black, and initially all nodes are white. There are two operations: `0 i`: Toggle the color of a node (black becomes white, white becomes black). `1 v`: Query the first black node on the path from $1$ to $v$; if none, output -1.

The first line contains $N$ and $Q$, the number of nodes and the number of operations. Lines $2$ through $N$ contain the $N-1$ undirected edges. Then $Q$ lines follow, each containing one operation `0 i` or `1 v`.

For each `1 v` operation, output the result.

For $1/3$ of the testdata, $N=5000,Q=400000$. For $1/3$ of the testdata, $N=10000,Q=300000$. For $1/3$ of the testdata, $N=100000, Q=100000$. In addition, $1 \le i,v \le N$. Translated by ChatGPT 5