注意事项

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

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

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

题目描述

题目译自 XXVII Olimpiada Informatyczna – Eliminacje do IOI Sieć

Bajtazar 是拜托克公司 BajtKom 的管理员。公司内有 $n$ 台服务器，服务器之间的连接网络呈树状拓扑结构，也就是说，从任意一台服务器到另一台服务器（直接或间接）都可以通过唯一一条连接路径传递信息（不允许回退）。

最近，Bajtazar 面临的一个重大挑战是计算机病毒，这些病毒由于来自敌对国家 Bitocji 的黑客攻击而出现在公司网络中。每个病毒都有一个特定的影响范围 $d$。当一个影响范围为 $d$ 的病毒攻击某台服务器时，它会干扰该服务器以及所有可以通过最多 $d$ 条直接连接到达的服务器的正常工作。

Bajtazar 拥有一款防病毒程序。在某台服务器上运行该程序可以清除该服务器上所有已感染的病毒。特别地，这会使得这些病毒不再干扰之前受其影响的服务器的工作。然而，Bajtazar 的防病毒程序无法为服务器提供未来的保护：一台被清理过的服务器在遭受新病毒攻击时仍会被再次感染。

你的任务是编写一个函数库，帮助收集 BajtKom 网络的安全数据。该函数库将接收有关病毒攻击和防病毒程序启动的信息，并负责报告在指定服务器对之间传递消息时的风险。风险定义为消息路径上的服务器数量（包括起始服务器和目标服务器），其中这些服务器的工作受到病毒干扰。

最后需要说明的是，公司内连接服务器的电缆是老式的，信号强度容易衰减。因此，通信路径长度限制为最多 $500$（这同时也是病毒的最大影响范围和消息传递的最大距离）。

交互方式

在本任务中，你需要用 C++ 编写一个与评测程序交互的函数库。你的函数库必须实现以下函数，这些函数将被评测程序调用（如果需要，你的解决方案可以包含其他函数）：

• initiuj(n)
  该函数在程序启动时只会被调用一次。调用此函数会通知函数库服务器总数 $n$。服务器编号从 $1$ 到 $n$。

  • C++ 接口：void inicjuj(int n);

• polaczenie(a, b)
  该函数将在 initiuj 函数调用后被调用 $n-1$ 次。调用此函数会通知函数库服务器编号 $a$ 和 $b$ 之间存在直接连接。每条直接连接的信息都会被通知且只通知一次。

  • C++ 接口：void polaczenie(int a, int b);

• wirus(a, d)
  调用此函数会通知函数库，一个病毒感染了编号为 $a$ $(1 \leq a \leq n)$ 的服务器，并开始干扰距离该服务器最多 $d$ $(0 \leq d \leq 500)$ 条直接连接内所有服务器的工作。

  • C++ 接口：void wirus(int a, int d);

• antywirus(a)
  调用此函数会通知函数库，防病毒程序清除了编号为 $a$ $(1 \leq a \leq n)$ 服务器上的所有病毒。

  • C++ 接口：void antywirus(int a);

• ryzyko(a, b)
  该函数是查询函数库关于传输消息风险的接口。调用此函数应返回连接编号为 $a$ 和 $b$ $(1 \leq a, b \leq n, a \neq b)$ 的服务器路径上，受病毒干扰的服务器数量。可以假设该路径包含的直接连接数不超过 $500$。

  • C++ 接口：int ryzyko(int a, int b);

你的程序不得从标准输入或文件读取任何数据，也不得向文件或标准输出写入任何内容。可以向标准错误输出（stderr）写入诊断信息，但请注意这会消耗运行时间。不要声明 main 函数。

你的函数库文件 sie.cpp 将与评测程序一起编译，命令如下：

g++ -O3 -static sie.cpp siegrader.cpp -std=c++17

样例

下表展示了函数调用序列的样例以及 ryzyko 函数的正确返回值。样例对应的连接网络结构如下图所示。

示例评测程序

为了便于你测试解决方案，我们在文件 siegrader.cpp 中提供了示例评测程序。要使用该程序，你应将解决方案文件 sie.cpp 放入同一目录下。

初始时，这些文件中可能包含任务的示例错误解决方案。我们还提供了示例文件 makefile，可以通过以下命令生成可执行文件 sieCPP.e：

make

生成的可执行文件会从标准输入读取函数名称及参数的列表，调用相应的函数，并将 ryzyko 函数返回的值按行输出到标准输出。

输入列表的格式如下：第一行应包含调用次数 $m$。接下来的 $m$ 行中，每行以字符 i、p、w、a 或 r 开头，分别表示调用函数 initiuj、polaczenie、wirus、antywirus 和 ryzyko。随后，每行包含一个或两个非负整数（视函数而定）作为调用参数。请注意，附带的评测程序不会检查输入格式是否正确，也不会验证是否符合「交互方式」和「数据范围与提示」的要求。

文件 sie0.in 描述了上述示例调用序列，文件 sie0.out 是相应的正确结果序列。

附加样例

1. $25$ 台服务器，其中 $7$ 台呈星形拓扑，每个外部服务器挂接 $3$ 台额外服务器；
2. $100$ 台服务器；网络呈星形拓扑；
3. $200$ 台服务器，全部位于单一路径上。

数据范围与提示

令 $q$ 表示 wirus、antywirus 和 ryzyko 的总调用次数。在所有子任务中，均满足 $1 \leq n \leq 1000000$ 且 $1 \leq q \leq 100000$。此外，如前所述，病毒影响范围及 ryzyko 函数中服务器间路径长度不超过 $500$。详细子任务附加限制及分值如下表所示。