{"problem":{"name":"[集训队互测 2022] 在路上","description":{"content":"**这是一道交互题，仅支持 C++ 提交**。 有一棵未知的树，**保证树的大小为奇数，你需要找到这棵树重心的编号**。 你可以进行询问，每次询问你可以询问三个点 $(x,y,z)$，若不存在一条简单路径同时经过三个点，则交互器会返回 $0$，否则若存在，那么交互器会返回三个点在路径上相对顺序中间的一个点。 令 $dis(a,b)$ 表示 $a,b$ 两点在树上最短路径经过的边数，你也可以理","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9056"},"statements":[{"statement_type":"Markdown","content":"**这是一道交互题，仅支持 C++ 提交**。\n\n有一棵未知的树，**保证树的大小为奇数，你需要找到这棵树重心的编号**。\n\n你可以进行询问，每次询问你可以询问三个点 $(x,y,z)$，若不存在一条简单路径同时经过三个点，则交互器会返回 $0$，否则若存在，那么交互器会返回三个点在路径上相对顺序中间的一个点。\n\n令 $dis(a,b)$ 表示 $a,b$ 两点在树上最短路径经过的边数，你也可以理解为:\n\n若 $dis(x,y)+dis(x,z)=dis(y,z)$，则交互器会返回 $x$。\n\n否则若 $dis(y,x)+dis(y,z)=dis(x,z)$，交互器会返回 $y$。\n\n否则若 $dis(z,x)+dis(z,y)=dis(x,y)$，交互器会返回 $z$。\n\n否则交互器会返回 $0$。\n\n在最终的测试中，每个测试点会包含 $T$ 组测试数据，和一个常数 $M$，表示你在所有测试数据中询问次数总和的上限，具体细则见 输入格式 以及 数据范围。\n\n#### 实现细节\n\n~~你需要引用 `path.h` 头文件。~~ 本题中你只需要把 `path.h` 头文件的内容粘贴到程序开头即可，不要引用 `path.h` 头文件。\n\n你需要实现下面的函数：\n\n```\nint centroid(int id,int N,int M);\n```\n\n其中 $id$ 为当前子任务的编号，$N$ 为当前询问树的大小，$M$ 为当前测试点剩余的询问次数，函数的返回值为当前树的重心编号。\n\n具体的，在第一次调用时 $M$ 为当前测试点的询问次数上限，每次调用结束之后 $M$ 会减去当前测试点使用的询问次数。\n\n你可以调用下面的函数：\n\n```\nint ask(int x,int y,int z);\n```\n\n表示你进行了一次询问，交互器会返回当前询问的答案，特别的，若询问次数已经超过了上限，交互器会返回 $-1$。\n\n注意同一个测试点中 `centroid` 函数可能会被多次调用，请注意数组清空等情况。\n\n**下发文件中有样例交互库，该交互库的实现与评测时的交互库几乎一致，如果对交互方式有不理解可以参照交互库的代码理解**。\n\n## Input\n\n样例评测库将读入如下格式的输入数据：\n\n第一行三个整数 $id,T,M$，表示当前的子任务编号以及测试数据的数量，以及询问次数的上界。\n\n对于每一组测试数据，第一行一个正整数 $n$，表示当前测试数据中树的大小。\n\n之后一行 $n-1$ 个正整数，第 $i$ 个数表示 $i+1$ 在以 $1$ 为根意义下的父亲节点。\n\n数据的答案将在交互库内部计算。\n\n## Output\n\n具体信息见交互库。\n\n[samples]\n\n## Background\n\n滥用本题评测者封号。\n\ndottle bot。\n\n## Note\n\n#### 数据范围\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/f3d6b2zv.png?x-oss-process=image/resize,m_lfit,h_1700,w_2250)\n\n特殊性质 $A$：保证树的形态为一条链，即每个点的度数均不超过 $2$。\n\n保证每个 Subtask 里的测试数据数量均不超过 $20$。**请仔细阅读每一档子任务及其限制**。\n\n#### 时空限制\n\nSubtask 5 时限为 3s。\n\nSubtask 7,8 时限为 4s。\n\n其余 Subtask 时限为 1s。\n\n空间限制：512MB。\n\n保证最终交互库的时间使用不超过  2s，空间使用不超过 64MB。\n\n#### 下发文件\n\n下发文件中有一个样例交互库，提供的交互头文件，一份示例代码，以及一个满足子任务 $4$ 性质的样例，选手也可以按照题目的输入格式构造其他样例。\n\n另外也有一份洛谷样式的交互库。\n\n保证下发的交互库和最终使用的交互库除反作弊之外没有区别，你可以使用这个交互库输出调试信息。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9056","tags":["集训队互测","2022","交互题","Special Judge","O2优化","树论","随机化"],"sample_group":[],"created_at":"2026-03-03 11:09:25"}}