P3459 [POI 2007] MEG-Megalopolis

Byteotia 最终也被全球化浪潮席卷，邮递员 Byteasar 也不例外。他曾经漫步在宁静的乡间小村中，如今却飞驰在高速公路上。但往昔那些悠闲的漫步，仍让他带着一丝温柔怀念。 过去，$n$ 个 Byteotia 村庄（编号 $1$ 至 $n$）通过双向泥土路相连，其结构满足： 从任意村庄出发到村庄 $1$（称为 Bitburg）存在唯一路径。 该路径仅经过编号小于等于起点村庄的村庄。 每条路直接连接两个不同村庄且不经过其他村庄。 道路不在村庄外交叉（但可能存在隧道或高架桥）。 岁月流转，乡间道路相继被改造成高速公路。Byteasar 清晰地记得每条路消失的时刻。如今，Byteotia 已无乡间小路——它们全被高速公路取代，将村庄连成了 Byteotia 大都市。 Byteasar 回想起他去各村送信的旅程。每次他从 Bitburg 出发，前往某个特定村庄。请你计算：对于每次发生在特定时刻、从 Bitburg 到指定村庄的旅程，他途经了多少条乡间道路。 ### 任务 编写程序实现： 1. 输入： - 初始道路连接描述 - 按时间顺序的事件序列（Byteasar 的旅程和道路改造事件） 2. 输出： - 对每次旅程，计算 Byteasar 经过的乡间道路数量

第一行：整数 $n$（$1 \le n \le 250,000$），表示村庄数。 接下来 $n-1$ 行：每行两个整数 $a, b$（$1 \le a < b \le n$），表示一条连接村庄 $a$ 和 $b$ 的初始道路。 下一行：整数 $m$（$1 \le m \le 250,000$），表示旅程次数。 接下来 $n+m-1$ 行：按时间顺序描述事件： - `A a b`（$a < b$）：村庄 $a$ 和 $b$ 间的道路被改造为高速公路。 - `W a`：Byteasar 从 Bitburg 出发到村庄 $a$ 的旅程查询。

输出 $m$ 行，每行一个整数，表示每次旅程中经过的乡间道路数量。

翻译：DeepSeek-R1