#P9597. [JOI Open 2018] 猫或狗

[JOI Open 2018] 猫或狗

题目背景

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

题目描述

你的儿子 JOI 君喜欢养宠物。在你家的花园里有 NN​ 个小屋可供饲养宠物,这 NN 个房子从 11NN 编号。有 N1N-1 条双向路径双向连接这 NN 个小屋,并且对于任意两个小屋,都可以通过某些路径在它们之间移动。每个小屋最多可以住一只宠物。

JOI 君想要养猫和狗,但是他很担心宠物们可能会经常打架。对于每个小屋的如下状态:住了一只猫,住了一只狗,没有住宠物,他都按如下方式定义了花园的危险级别

  • 对于每只猫和每只狗,为了不让他们通过未阻塞的道路相遇,需要阻塞的最小路径数。

在定义危险级别后,JOI 君开始指定后 QQ 天使用花园的计划。初始时,所有小屋里都没有宠物。第 ii 天的计划是如下内容中的一个:

  • 在目前没有宠物的小屋 vv​​ 中养一只猫。
  • 在目前没有宠物的小屋 vv 中养一只狗。
  • 将小屋 vv 中的宠物送给邻居,这意味着在小屋 vv​ 中就没有宠物了。

你作为家长,有责任检查你的儿子的计划是否危险。更确切地说,你需要求出这 QQ 天每天进行完计划后,这个花园的危险级别。


为了在线地回答询问,本题采用交互的方式进行评测。

你需要实现四个函数 initializecatdogneighbor

最初,函数 initialize 被调用。这个函数的作用是接受花园的信息。

  • initialize(N, A, B)
    • NN:花园中小屋的数量。
    • A,BA, B:长度为 N1N-1 的数组。意味着对于 0iN20\le i\le N-2,在小屋 AiA_i 和小屋 BiB_i 之间存在一条路径。保证对于任意两个不同的小屋,沿某些路径可以在它们之间移动。

然后,对于这 QQ 天的计划,按时间顺序会调用如下函数:

  • cat(v):调用此函数,在目前没有宠物的小屋 vv 中养一只猫。
  • dog(v):调用此函数,在目前没有宠物的小屋 vv 中养一只狗。
  • neighbor(v):调用此函数,让小屋 vv 中的宠物离开。

这些函数应返回在这个计划执行后花园的危险值。

目前不支持对 Java 和 Pascal 语言提交的测评。

输入格式

样例交互器按如下格式读取输入:

第一行一个整数 NN

接下来 N1N-1 行,每行两个整数 Ai,BiA_i,B_i

接下来一行一个整数 QQ

接下来 QQ 行,每行两个整数 Tj,vjT_j,v_j

这里,如果在第 jj 天的调用是 cat\texttt{cat},则 Tj=1T_j=1,如果是 dog\texttt{dog},则 Tj=2T_j=2,如果是 neighbor\texttt{neighbor},则 Tj=3T_j=3

输出格式

样例交互器按如下格式输出第 jj 天的函数调用结果 DjD_j

jj 行输出 DjD_j

3
1 2
2 3
4
1 1
1 3
2 2
3 2

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

提示

【样例】

考虑有 55 个小屋和 44 条路径的情况。这四条路径连接小屋 11 和小屋 22,小屋 22 和小屋 33,小屋 22 和小屋 44,小屋 44 和小屋 55

  1. 假设他首先在小屋 33 养了一只猫,在小屋 55 养了一只狗。通过阻塞小屋 22 和小屋 44 之间的道路,他可以避免猫和狗相遇。因此,此时的危险等级是 11
  2. 假设他之后在小屋 22​ 养了一直新猫,在小屋 11​ 养了一只新狗。通过阻塞小屋 22​ 和小屋 44​ 之间的道路与小屋 11​ 和小屋 22​ 之间的道路,他可以避免猫和狗相遇。因此,此时的危险等级是 22
  3. 假设他最后将小屋 22 的猫给了邻居。他只需要阻塞小屋 22 和小屋 33 之间的道路。因此,此时的危险等级是 11

【数据范围】

本题有三个子任务。每个子任务的分值与附加限制如下表所示:

子任务编号 分值 NN QQ
11 88 1N151\le N\le 15 1Q1001\le Q\le 100
22 3030 1N1 0001\le N\le 1\ 000 1Q1 0001\le Q\le 1\ 000
33 6262 1N100 0001\le N\le 100\ 000 1Q100 0001\le Q\le 100\ 000