{"raw_statement":[{"iden":"statement","content":"你用销售机器人的利润雇佣了一名助手，现在你准备好去拿走装有 CEOI 奖章的保险箱了。\n\n保险箱位于一所由 $n$ 个房间所组成的大学建筑内，这些房间由 $n-1$ 扇门连接。每个房间都可以从其他任何房间到达，且每个房间最多与 $3$ 扇门相连。  \n你和你的助手都有描述建筑物内房间相连情况的平面图，但是你们两个各自拥有的平面图虽然描述了相同的房间结构布局，但是房间和门的编号可能不同。\n\n在比赛的第二天，委员会忙于处理赛时通知和选手提问。这将是接近装着奖牌的保险箱的完美机会。\n\n你的助手会首先搜索整栋大楼。一旦他找到保险箱所在的房间，它就会给你留下前往那个房间的提示。由于手机不能带进赛场，他用了去年 BOI 留下的几乎无限供应的领带。由于这些领带完全相同无法区分，你能获得的信息就是他在任何给定房间里所留下的领带数量。由于一个房间内过多的领带非常可疑，因此任何单个房间内领带的最大数量应当尽可能少（参阅评分部分）。\n\n之后，你计划在上厕所的时候溜出去，利用助手留下来的领带找到有保险箱的房间。保险箱藏在房间里，所以你进入带有保险箱的房间时，必须依靠领带识别这个房间；此外，由于“上厕所”时间过长会被发现，你必须尽快找到保险箱。你最多可以走过 $d+30$ 扇门，其中 $d$ 是你的初始位置到保险箱所在位置的最短路径上的门数量。若重复穿过同一扇门，则每次都计入。\n\n因此，你需要编写一个程序，告诉助手需要在每个房间留下多少条领带，并引导你前往带有保险箱的房间。"},{"iden":"input","content":"本题为函数交互题。\n\n对于每个测试点，你的程序会运行两次。\n\n你需要实现如下两个函数（函数原型已给出）：\n```\nvector<int> mark(vector<pair<int,int>> F, int safe);\n```\n- $F$: 包含了 $n-1$ 个二元组 $(u,v)$，其中 $1 \\le u,v \\le n$ 并且保证 $u \\neq v$，代表在助手的地图上，$u$ 号房间和 $v$号房间之间由一扇门相连。\n- $\\mathrm{safe}$: 表示你的助手的地图上保险箱所在的房间编号。\n\n该函数应当返回一个长度为 $n$ 的 `vector<int>` $v$，其中每个元素 $v_i$ 代表你的助手应当在他地图上 $i+1$ 号房间留下的领带数量。你应当保证 $0 \\le v_i \\le 10^9$。\n\n```\nvoid locate(vector<pair<int,int>> F,int curr,int t);\n```\n- $F$: 包含了 $n-1$ 个二元组 $(u,v)$，其中 $1 \\le u,v \\le n$ 并且保证 $u \\neq v$，代表在你的地图上，$u$ 号房间和 $v$号房间之间由一扇门相连。\n- $\\mathrm{curr}$: 你目前所在的房间编号。\n- $t$: 在你当前所处的房间中，找到的领带数量。\n\n在如下的叙述中，房间编号采用你地图的编号方案。\n\n在实现函数 `locate` 的过程中，你可以调用如下函数：\n```\nint visit(int v);\n```\n以此来从你目前所在的房间 $u$ 移动到一个相邻的房间 $v$。你需要保证操作合法，即 $1 \\le v \\le n,(u,v) \\in F\\:\\vee (v,u) \\in F$。\n\n该函数返回一个非负整数 $k$，表示你在房间 $v$ 中找到的领带个数。\n\n该函数调用的次数不应超过 $d+30$，其中 $d$ 是你的起点到终点的最短距离。\n\n当函数 `locate` 终止时，你应当处于带有保险箱的房间内。\n\n对于每个测试点，第一次运行程序时调用 `mark`，第二次调用 `locate`。\n\n如果 `visit` 调用次数过多、调用不合法或在 `mark` 中被调用，你的程序将会被终止运行，提交将会被判**错误**。  \n你的程序不得写入或读取 `stdin` 或 `stdout`，否则将会被判**违反安全规定**。  \n但是你可以随便往 `stderr` 输出，没人管这个。\n\n你需要在源代码文件开头加上 `#include \"incursion.h\"`。\n\n你应当将程序与 `sample_grader.cpp` 链接以进行本地测试。\n\n下面是示例评分器的说明，请参阅 `sample_grader.cpp` 以获取操作说明。\n\n为简单起见，本评分器不会运行你的程序两次，而是在一次运行中调用两个函数各一次。附件中包含了一个 `sample_grader.cpp` 的示例实现。\n\n注意：该实现不与评测所用的实现相同，禁止采用 Hack 评分器的方式试图通过本题！\n"},{"iden":"note","content":"### 评分细则\n\n共有 4 个 subtask。对于每个测试点，$2 \\le n \\le 45000$。\n\nSubtask 1 (30 points)，保证没有一个房间有三扇门相连。\nSubtask 2 (30 points). 有且仅有一个房间有两扇门相连。\nSubtask 3 (40 points). 没有特殊性质。\n\n对于每个测试点，假设使用领带最多的房间用了 $T_{\\max}$ 条领带，\n- $T_{\\max}<2$，你将会获得该测试点 $100\\%$ 的分数。\n- $T_{\\max}=2$，你将会获得该测试点 $40\\%$ 的分数。\n- $2 < T_{\\max} \\le 10^9$，你将会获得该测试点 $30\\%$ 的分数。\n\n### 交互库使用方法\n**注意洛谷提供的交互库与原版不同。**\n\n请使用 `g++ -std=c++17 -Wall -O2 -o test interactive_lib.cpp xxx.cpp` 编译，其中 `xxx.cpp` 是你的程序名字。\n\n示例交互库首先从标准输入读入三个正整数, $n$, $s$, $seed$，表示点数、起点的原编号、随机数种子。\n\n然后读入 $n-1$ 行，每行两个正整数 $u,v$，表示原树的一条边。其中需保证 $1 \\le u < v \\le n$。\n然后读入一行一个字符串，表示打乱规则。\n\n**你不需要在意打乱序号的具体实现。该实现与最终评测所用交互库不一定相同。**\n\n接下来交互库将会调用一次 `mark`，一次 `locate`。注意交互库可能会打乱序号。\n\n交互库可能向终端输出以下信息：\n\n- `Invalid input.` 输入不合法。\n- `Invalid call to visit. (ALICE CALLED VISIT)` 在 `mark` 中调用 `visit`。\n- `Invalid call to visit. (INDEX ERROR)` 访问了不合法的点。\n- `Invalid call to visit. (NOT CONNECTED)` 访问的点和当前所在的点没有直接的边相连。\n- `Invalid call to visit. (TOO MANY VISITS)` 调用 `visit` 次数过多。\n- `Invalid return value of mark.` `mark` 的返回值不合法。即返回的 `vector` 长度不为 $n$ 或者有小于 $0$ 或大于 $10^9$ 的数。\n- `Not correct: current position is X` 最终并不在目标点，你应该在 $X$ 点（在第二张地图上）。\n- `Correct: at most X tie(s) per room.` 到达目标点，且用领带最多的房间使用了 X 条领带。\n\n最终评测时，只会返回正确与否的信息。"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}