P8844 [Chuanzhi Cup #4 Preliminary] Xiao Ka and Fallen Leaves

Sitting on a fast-moving train and looking at the yellowing leaves outside the window, Xiao Ka thought, “Another winter.” This is a season when everything withers. When a cold wind blows, the leaves turn yellow; when another cold wind blows, the ground becomes covered in gold. Out of boredom, Xiao Ka discovered that leaves turn yellow following a pattern: on every tree, only the lower half is yellow, and the upper part is all green. Xiao Ka wondered how to count the number of yellow leaves.

You are given a rooted tree with $n(1\le n\le 10^5)$ nodes. The root is node $1$, and the depth of the root is $1$. Initially, all nodes in the entire tree are green. Xiao Ka has $m(1\le m \le 10^5)$ operations. Operation 1: Recolor the whole tree to green, then make all nodes with depth $\ge x$ turn yellow. Operation 2: Query how many yellow nodes are in the subtree of a node $x$.

The first line contains two positive integers $n,m$, denoting the number of nodes in the tree and the number of operations. The next $n-1$ lines each contain two positive integers $x,y$, denoting an edge in the tree. The next $m$ lines each contain two positive integers $op,x(1\le x\le n)$. If $op=1$, it means Operation 1; otherwise, it means Operation 2.

For each Operation 2, output one line with one positive integer, denoting the number of yellow nodes in the subtree of $x$.

The tree in Sample 1 is as follows:  In the first coloring, nodes $4$ and $5$ are colored yellow. Querying the subtrees of nodes $5,2,1$, the answers are $1,2,2$, respectively. In the second coloring, nodes $2,3,4,5$ are colored yellow. Querying the subtrees of nodes $1,4,5,2$, the answers are $4,2,1,3$, respectively. Translated by ChatGPT 5