注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "particles.h"。

题目描述

题目译自 2025년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사 T2 「입자 가속기」

KOI 研究所正在利用粒子加速器进行研究。这台粒子加速器由 $N$ 个房间和连接这些房间的 $N-1$ 条双向通道组成。你可以通过这些通道在任意两个不同房间之间自由往返。换句话说，KOI 研究所的粒子加速器形成了一个树形结构。

加速器的每个房间被编号为 $0$ 到 $N-1$，互不相同；每条通道则被编号为 $0$ 到 $N-2$，同样互不重复。对于任意 $0 \leq i \leq N-2$，第 $i$ 条通道连接的是 $A[i]$ 号房间和 $B[i]$ 号房间。

最近，KOI 研究所启动了 IOI 粒子碰撞实验。由于生成 IOI 粒子极为困难，每个房间最多只能尝试生成一次。如果某个房间成功生成 IOI 粒子，那么一颗 IOI 粒子会静止地停留在该房间中；如果生成失败，该房间将被封闭以检修设备，无法再次使用。

KOI 研究所计划挑选若干房间尝试生成 IOI 粒子，然后开展实验。实验包含多次碰撞实验，按顺序进行。每次碰撞实验需要选择两个含有 IOI 粒子的房间进行碰撞，但连接这两个房间的路径上不得有其他含 IOI 粒子的房间，也不得有因生成失败而封闭的房间。一次碰撞实验结束后，参与实验的两个粒子会消失。注意，如果某个房间成功生成了 IOI 粒子，但该粒子后来因碰撞消失，那么在后续实验中，这间房间即使出现在连接路径上也不会有影响。

你的任务是帮助 KOI 研究所计算最多能进行多少次碰撞实验。初始时，加速器中所有房间都没有 IOI 粒子，且每个房间都可以尝试生成粒子。研究所总共会尝试 $Q$ 次粒子生成，你需要针对每次生成尝试，计算当前状态下最多能进行多少次碰撞实验。

实现细节

你需要实现以下函数：

void initialize(int N, std::vector<int> A, std::vector<int> B)

• N：粒子加速器中的房间数量。
• A, B：大小为 $N-1$ 的整数数组。对于任意 $0 \leq i \leq N-2$，表示存在一条通道连接 $A[i]$ 号房间和 $B[i]$ 号房间。
• 该函数只会在初始化时调用一次。

int generate(int v, bool result)

• 该函数表示在 $v$ 号房间尝试生成 IOI 粒子。
• 在 initialize 函数调用后，该函数会被调用 $Q$ 次。
• v：尝试生成粒子的房间编号。保证在此函数调用前，$v$ 号房间未尝试过生成粒子。
• result：生成结果。如果为 true，表示生成成功，$v$ 号房间将含有一颗 IOI 粒子；如果为 false，表示生成失败，$v$ 号房间将被封闭，无法使用。
• 该函数需返回当前状态下最多能进行的碰撞实验次数。

样例

假设 $N=6$，$A=[0,0,0,3,3]$，$B=[1,2,3,4,5]$。

评测程序会先调用：

initialize(6, [0, 0, 0, 3, 3], [1, 2, 3, 4, 5])

下图展示了 KOI 研究所粒子加速器的结构。

假设 $1$ 号房间成功生成 IOI 粒子，评测程序调用：

generate(1, true)

下图展示了粒子加速器的现状。此时，$1$ 号房间含有一颗 IOI 粒子。由于只有一个粒子，无法进行碰撞实验，函数应返回 $0$。

接着，假设 $5$ 号房间也成功生成 IOI 粒子，评测程序调用：

generate(5, true)

下图展示了粒子加速器的现状。现在，$1$ 号和 $5$ 号房间各有一颗 IOI 粒子。选择 $1$ 号和 $5$ 号房间可进行一次碰撞实验，但无法进行更多次，因此函数应返回 $1$。

再假设 $0$ 号房间生成失败，评测程序调用：

generate(0, false)

下图展示了粒子加速器的现状。此时，$1$ 号和 $5$ 号房间仍有 IOI 粒子，$0$ 号房间被封闭。由于 $1$ 号和 $5$ 号房间的路径上包含封闭的 $0$ 号房间，无法进行碰撞实验，函数应返回 $0$。

接着，假设 $4$ 号房间成功生成 IOI 粒子，评分程序调用：

generate(4, true)

下图展示了粒子加速器的现状。现在，$1$、$4$、$5$ 号房间含 IOI 粒子，$0$ 号房间封闭。选择 $4$ 号和 $5$ 号房间可进行一次碰撞实验（路径上无其他粒子或封闭房间），但无法进行更多次，函数应返回 $1$。

最后，假设 $3$ 号房间成功生成 IOI 粒子，评测程序调用：

generate(3, true)

下图展示了粒子加速器的现状。当前，$1$、$3$、$4$、$5$ 号房间含 IOI 粒子，$0$ 号房间封闭。$4$ 号和 $5$ 号房间路径上有 $3$ 号房间，无法碰撞；但 $3$ 号和 $5$ 号房间可进行一次碰撞实验。

下图是选择 $3$ 号房间和 $5$ 号房间进行碰撞实验后，粒子加速器的状态。由于 $0$ 号房间位于连接 $1$ 号房间和 $4$ 号房间的路径上，因此无法进行碰撞实验。由于任何碰撞实验都无法进行多次，因此该函数必须返回 $1$。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq Q \leq N \leq 200000$
• KOI 研究所的粒子加速器为树形结构。
• 对于所有 $0 \leq i \leq N-2$，$0 \leq A[i], B[i] \leq N-1$ 且 $A[i] \neq B[i]$。
• 每次 generate 函数调用的 $v$ 满足 $0 \leq v \leq N-1$，且各次调用的 $v$ 值互不相同。

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$9$	$2 \leq Q \leq N \leq 5000$
$2$	$16$	对于所有 $0 \leq i \leq N-2$，$A[i] = i$，$B[i] = i+1$
$3$	$20$	result = false 的 generate 函数调用次数最多为 $20$ 次
$4$	$23$	result = true 的 generate 函数调用次数最多为 $20$ 次
$5$	$32$	无附加限制

示例评测程序

示例评测程序接收以下格式的输入：

• 第 $1$ 行：$N\ Q$
• 第 $2+i$ $(0 \leq i \leq N-2)$ 行：$A[i]\ B[i]$
• 第 $N+1+j$ $(0 \leq j \leq Q-1)$ 行：$v\ result$（$result$ 为 true 输入 $1$，为 false 输入 $0$）

输出格式：

• 第 $1+j$ $(0 \leq j \leq Q-1)$ 行：第 $j$ 次 generate 函数的返回值

请注意，示例评测程序可能与实际评测程序有所不同。