P4092 [HEOI2016/TJOI2016] 树

在 2016 年，佳媛姐姐刚刚学习了树，非常开心。现在他想解决这样一个问题：给定一颗有根树，根为 $1$ ，有以下两种操作： 1. 标记操作：对某个结点打上标记。（在最开始，只有结点 $1$ 有标记，其他结点均无标记，而且对于某个结点，可以打多次标记。） 2. 询问操作：询问某个结点最近的一个打了标记的祖先。（这个结点本身也算自己的祖先） 你能帮帮她吗?

无

无

$30\%$ 的数据，$1 \leqslant N, Q \leqslant 1000$ ； $70\%$ 的数据，$1 \leqslant N, Q \leqslant 10000$ ； $100\%$ 的数据，$1 \leqslant N, Q \leqslant 100000$ 。