4391. 粒子对撞

【题目描述】

小 H 和小 L 正在玩一个粒子碰撞的游戏。游戏在包含 $n$ 个节点的无根树上进行，节点编号为 $0 \sim n-1$。

初始时，每个节点上都没有粒子。游戏共有 $q$ 次操作，每次操作给定 $u, \mathrm{result}$，表示尝试在节点 $u$ 生成一个粒子：

• 若生成成功（$\mathrm{result}=\mathrm{true}$），$u$ 上将存在一个粒子。
• 若生成失败（$\mathrm{result}=\mathrm{false}$），$u$ 将被永久关闭，无法使用。

我们保证每个节点最多尝试生成 $1$ 次。

一次碰撞实验流程如下：选择两个（不同的）节点 $u, v$，满足：

• $u, v$ 上当前存在粒子；
• $u, v$ 路径上没有其他粒子存在；
• $u, v$ 路径上没有被关闭的节点。

碰撞后，$u, v$ 上的粒子将被销毁。$u, v$ 节点本身在粒子销毁后变为空节点，之后可以出现在其他路径中。

在每次尝试生成后，小 L 需要回答当前状态下至多能够进行多少次碰撞实验。注意：小 L 只需要计算理论上的最大次数，并不需要真正模拟碰撞销毁过程。

【实现细节】

选手不需要，也不应该实现 main 函数。

选手需要确保提交的程序包含头文件 nuclear.h，即在程序开头加入以下代码：

#include "nuclear.h"

选手需要在提交的程序源文件 nuclear.cpp 中实现以下两个函数：

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

• $n$ 表示树的节点数量。
• $A, B$ 是长度为 $n-1$ 的数组，表示树的第 $i$ 条边连接 $A_i$ 和 $B_i$。
• 对于每个测试点，该函数会在程序开始运行时被交互库调用恰好一次。

int generate(int u, bool result);

• $u$ 表示当前操作的节点编号。
• $\mathrm{result}$ 表示生成结果。
• 该函数需要返回一个非负整数，表示当前状态下至多能够进行的碰撞实验次数。
• 对于每个测试点，该函数会被交互库调用恰好 $q$ 次。

【测试程序方式】

可执行文件将从标准输入读入以下格式的数据：

• 第一行包含两个正整数 $n, q$。
• 接下来 $n-1$ 行，每行两个整数 $A_i, B_i$。
• 接下来 $q$ 行，每行包含一个整数 $u_i$ 和一个整数 $\mathrm{result}_i$（$1$ 代表 true，$0$ 代表 false）。

【样例输入 #1】

6 5
0 1
0 2
0 3
3 4
3 5
1 1
5 1
0 0
4 1
3 1

【样例输出 #1】

0
1
0
1
1