A5713. 「TJOI / HEOI2016」树
编程题
省选/NOI-
知识点
题目描述
在 2016 年，佳媛姐姐刚刚学习了树，非常开心。现在他想解决这样一个问题：给定一颗有根树（根为 $1$），有以下两种操作：
1. 标记操作：对某个结点打上标记（在最开始，只有结点 $1$ 有标记，其他结点均无标记，而且对于某个结点，可以打多次标记）。
2. 询问操作：询问某个结点最近的一个打了标记的祖先（这个结点本身也算自己的祖先）。
你能帮帮他吗?
1. 标记操作：对某个结点打上标记（在最开始，只有结点 $1$ 有标记，其他结点均无标记，而且对于某个结点，可以打多次标记）。
2. 询问操作：询问某个结点最近的一个打了标记的祖先（这个结点本身也算自己的祖先）。
你能帮帮他吗?
输入格式
输入第一行两个正整数 $N$ 和 $Q$ 分别表示节点个数和操作次数。
接下来 $N-1$ 行，每行两个正整数 $u , v$（$1 \leq u,v \leq n$）表示 $u$ 到 $v$ 有一条有向边。
接下来 $Q$ 行，形如 $\text{oper}\ \text{num}$。$\text{oper}$ 为
接下来 $N-1$ 行，每行两个正整数 $u , v$（$1 \leq u,v \leq n$）表示 $u$ 到 $v$ 有一条有向边。
接下来 $Q$ 行，形如 $\text{oper}\ \text{num}$。$\text{oper}$ 为
C 时表示这是一个标记操作，$\text{oper}$ 为 Q 时表示这是一个询问操作。输出格式
输出一个正整数，表示结果。
输入输出样例
输入 #1
5 5 1 2 1 3 2 4 2 5 Q 2 C 2 Q 2 Q 5 Q 3
输出 #1
1 2 2 1
说明/提示
对于每次询问操作，$1 \leq N, Q \leq 100000$。