P9597 [JOI Open 2018] 猫或狗

题目背景

**特别提醒,由于洛谷交互机制的特殊性,你不能在程序中引用 `catdog.h`,只需要实现要求的几个函数即可。**

题目描述

你的儿子 JOI 君喜欢养宠物。在你家的花园里有 $N$​ 个小屋可供饲养宠物,这 $N$ 个房子从 $1$ 到 $N$ 编号。有 $N-1$ 条双向路径双向连接这 $N$ 个小屋,并且对于任意两个小屋,都可以通过某些路径在它们之间移动。每个小屋最多可以住一只宠物。 JOI 君想要养猫和狗,但是他很担心宠物们可能会经常打架。对于每个小屋的如下状态:住了一只猫,住了一只狗,没有住宠物,他都按如下方式定义了花园的**危险级别**: - 对于每只猫和每只狗,为了不让他们通过未阻塞的道路相遇,需要阻塞的最小路径数。 在定义危险级别后,JOI 君开始指定后 $Q$ 天使用花园的计划。初始时,所有小屋里都没有宠物。第 $i$ 天的计划是如下内容中的一个: - 在目前没有宠物的小屋 $v$​​ 中养一只猫。 - 在目前没有宠物的小屋 $v$ 中养一只狗。 - 将小屋 $v$ 中的宠物送给邻居,这意味着在小屋 $v$​ 中就没有宠物了。 你作为家长,有责任检查你的儿子的计划是否危险。更确切地说,你需要求出这 $Q$ 天每天进行完计划后,这个花园的危险级别。 --- **为了在线地回答询问,本题采用交互的方式进行评测。** 你需要实现四个函数 `initialize`,`cat`,`dog` 和 `neighbor`。 最初,函数 `initialize` 被调用。这个函数的作用是接受花园的信息。 - `initialize(N, A, B)` - $N$:花园中小屋的数量。 - $A, B$:长度为 $N-1$ 的数组。意味着对于 $0\le i\le N-2$,在小屋 $A_i$ 和小屋 $B_i$ 之间存在一条路径。保证对于任意两个不同的小屋,沿某些路径可以在它们之间移动。 然后,对于这 $Q$ 天的计划,按时间顺序会调用如下函数: - `cat(v)`:调用此函数,在目前没有宠物的小屋 $v$ 中养一只猫。 - `dog(v)`:调用此函数,在目前没有宠物的小屋 $v$ 中养一只狗。 - `neighbor(v)`:调用此函数,让小屋 $v$ 中的宠物离开。 这些函数应返回在这个计划执行后花园的危险值。 目前不支持对 Java 和 Pascal 语言提交的测评。

输入格式

输出格式

说明/提示

**【样例】** 考虑有 $5$ 个小屋和 $4$ 条路径的情况。这四条路径连接小屋 $1$ 和小屋 $2$,小屋 $2$ 和小屋 $3$,小屋 $2$ 和小屋 $4$,小屋 $4$ 和小屋 $5$。 1. 假设他首先在小屋 $3$ 养了一只猫,在小屋 $5$ 养了一只狗。通过阻塞小屋 $2$ 和小屋 $4$ 之间的道路,他可以避免猫和狗相遇。因此,此时的危险等级是 $1$。 2. 假设他之后在小屋 $2$​ 养了一直新猫,在小屋 $1$​ 养了一只新狗。通过阻塞小屋 $2$​ 和小屋 $4$​ 之间的道路与小屋 $1$​ 和小屋 $2$​ 之间的道路,他可以避免猫和狗相遇。因此,此时的危险等级是 $2$。 3. 假设他最后将小屋 $2$ 的猫给了邻居。他只需要阻塞小屋 $2$ 和小屋 $3$ 之间的道路。因此,此时的危险等级是 $1$。 **【数据范围】** 本题有三个子任务。每个子任务的分值与附加限制如下表所示: | 子任务编号 | 分值 | $N$ | $Q$ | | :--------: | :--: | :------------------: | :------------------: | | $1$ | $8$ | $1\le N\le 15$ | $1\le Q\le 100$ | | $2$ | $30$ | $1\le N\le 1\ 000$ | $1\le Q\le 1\ 000$ | | $3$ | $62$ | $1\le N\le 100\ 000$ | $1\le Q\le 100\ 000$ |