P4092 [HEOI2016/TJOI2016] Tree

In 2016, Jiayuan jiejie had just learned about trees and was very happy. Now she wants to solve the following problem: given a rooted tree with root $1$, there are two types of operations: 1. Mark operation: put a mark on some node. (At the very beginning, only node $1$ is marked, and all other nodes are unmarked. You may mark the same node multiple times.) 2. Query operation: ask for the nearest marked ancestor of some node (the node itself also counts as its own ancestor). Can you help her?

The first line contains two positive integers $N$ and $Q$, denoting the number of nodes and the number of operations. The next $N-1$ lines each contain two positive integers $u, v$ ($1 \leqslant u, v \leqslant N$) indicating a directed edge from $u$ to $v$. These edges form a rooted tree with root $1$, and edges are directed from parent to child. The next $Q$ lines are of the form `oper num`. When `oper` is `C`, it denotes a mark operation on node `num`. When `oper` is `Q`, it denotes a query operation on node `num`.

For each query operation, output one integer: the nearest marked ancestor of the given node (including the node itself). Print each answer on its own line.

- 30% of the testdata: $1 \leqslant N, Q \leqslant 1000$. - 70% of the testdata: $1 \leqslant N, Q \leqslant 10000$. - 100% of the testdata: $1 \leqslant N, Q \leqslant 100000$. Translated by ChatGPT 5