{"problem":{"name":"[JOI Open 2018] 猫或狗 / Cats or Dogs","description":{"content":"你的儿子 JOI 君喜欢养宠物。在你家的花园里有 $N$​ 个小屋可供饲养宠物，这 $N$ 个房子从 $1$ 到 $N$ 编号。有 $N-1$ 条双向路径双向连接这 $N$ 个小屋，并且对于任意两个小屋，都可以通过某些路径在它们之间移动。每个小屋最多可以住一只宠物。 JOI 君想要养猫和狗，但是他很担心宠物们可能会经常打架。对于每个小屋的如下状态：住了一只猫，住了一只狗，没有住宠物，他都按如下方","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9597"},"statements":[{"statement_type":"Markdown","content":"你的儿子 JOI 君喜欢养宠物。在你家的花园里有 $N$​ 个小屋可供饲养宠物，这 $N$ 个房子从 $1$ 到 $N$ 编号。有 $N-1$ 条双向路径双向连接这 $N$ 个小屋，并且对于任意两个小屋，都可以通过某些路径在它们之间移动。每个小屋最多可以住一只宠物。\n\nJOI 君想要养猫和狗，但是他很担心宠物们可能会经常打架。对于每个小屋的如下状态：住了一只猫，住了一只狗，没有住宠物，他都按如下方式定义了花园的**危险级别**：\n\n- 对于每只猫和每只狗，为了不让他们通过未阻塞的道路相遇，需要阻塞的最小路径数。\n\n在定义危险级别后，JOI 君开始指定后 $Q$ 天使用花园的计划。初始时，所有小屋里都没有宠物。第 $i$ 天的计划是如下内容中的一个：\n\n- 在目前没有宠物的小屋 $v$​​ 中养一只猫。\n- 在目前没有宠物的小屋 $v$ 中养一只狗。\n- 将小屋 $v$ 中的宠物送给邻居，这意味着在小屋 $v$​ 中就没有宠物了。\n\n你作为家长，有责任检查你的儿子的计划是否危险。更确切地说，你需要求出这 $Q$ 天每天进行完计划后，这个花园的危险级别。\n\n---\n\n**为了在线地回答询问，本题采用交互的方式进行评测。**\n\n你需要实现四个函数 `initialize`，`cat`，`dog` 和 `neighbor`。\n\n最初，函数 `initialize` 被调用。这个函数的作用是接受花园的信息。\n\n- `initialize(N, A, B)`\n  - $N$：花园中小屋的数量。\n  - $A, B$：长度为 $N-1$ 的数组。意味着对于 $0\\le i\\le N-2$，在小屋 $A_i$ 和小屋 $B_i$ 之间存在一条路径。保证对于任意两个不同的小屋，沿某些路径可以在它们之间移动。\n\n然后，对于这 $Q$ 天的计划，按时间顺序会调用如下函数：\n\n- `cat(v)`：调用此函数，在目前没有宠物的小屋 $v$ 中养一只猫。\n- `dog(v)`：调用此函数，在目前没有宠物的小屋 $v$ 中养一只狗。\n- `neighbor(v)`：调用此函数，让小屋 $v$ 中的宠物离开。\n\n这些函数应返回在这个计划执行后花园的危险值。\n\n目前不支持对 Java 和 Pascal 语言提交的测评。\n\n## Input\n\n样例交互器按如下格式读取输入：\n\n第一行一个整数 $N$。\n\n接下来 $N-1$ 行，每行两个整数 $A_i,B_i$。\n\n接下来一行一个整数 $Q$。\n\n接下来 $Q$ 行，每行两个整数 $T_j,v_j$。\n\n这里，如果在第 $j$ 天的调用是 $\\texttt{cat}$，则 $T_j=1$，如果是 $\\texttt{dog}$，则 $T_j=2$，如果是 $\\texttt{neighbor}$，则 $T_j=3$。\n\n## Output\n\n样例交互器按如下格式输出第 $j$ 天的函数调用结果 $D_j$：\n\n第 $j$ 行输出 $D_j$。\n\n[samples]\n\n## Background\n\n**特别提醒，由于洛谷交互机制的特殊性，你不能在程序中引用 `catdog.h`，只需要实现要求的几个函数即可。**\n\n## Note\n\n**【样例】**\n\n考虑有 $5$ 个小屋和 $4$ 条路径的情况。这四条路径连接小屋 $1$ 和小屋 $2$，小屋 $2$ 和小屋 $3$，小屋 $2$ 和小屋 $4$，小屋 $4$ 和小屋 $5$。\n\n1. 假设他首先在小屋 $3$ 养了一只猫，在小屋 $5$ 养了一只狗。通过阻塞小屋 $2$ 和小屋 $4$ 之间的道路，他可以避免猫和狗相遇。因此，此时的危险等级是 $1$。\n2. 假设他之后在小屋 $2$​ 养了一直新猫，在小屋 $1$​ 养了一只新狗。通过阻塞小屋 $2$​ 和小屋 $4$​ 之间的道路与小屋 $1$​ 和小屋 $2$​ 之间的道路，他可以避免猫和狗相遇。因此，此时的危险等级是 $2$。\n3. 假设他最后将小屋 $2$ 的猫给了邻居。他只需要阻塞小屋 $2$ 和小屋 $3$ 之间的道路。因此，此时的危险等级是 $1$。\n\n**【数据范围】**\n\n本题有三个子任务。每个子任务的分值与附加限制如下表所示：\n\n| 子任务编号 | 分值 |         $N$          |         $Q$          |\n| :--------: | :--: | :------------------: | :------------------: |\n|    $1$     | $8$  |    $1\\le N\\le 15$    |   $1\\le Q\\le 100$    |\n|    $2$     | $30$ |  $1\\le N\\le 1\\ 000$  |  $1\\le Q\\le 1\\ 000$  |\n|    $3$     | $62$ | $1\\le N\\le 100\\ 000$ | $1\\le Q\\le 100\\ 000$ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9597","tags":["2018","交互题","O2优化","JOI（日本）"],"sample_group":[["3\n1 2\n2 3\n4\n1 1\n1 3\n2 2\n3 2\n","0\n0\n2\n0"],["5\n1 2\n2 3\n2 4\n4 5\n5\n1 3\n2 5\n1 2\n2 1\n3 2","0\n1\n1\n2\n1"]],"created_at":"2026-03-03 11:09:25"}}