[CEOI2023] The Ties That Guide Us (incursion)

你用销售机器人的利润雇佣了一名助手，现在你准备好去拿走装有 CEOI 奖章的保险箱了。 保险箱位于一所由 $n$ 个房间所组成的大学建筑内，这些房间由 $n-1$ 扇门连接。每个房间都可以从其他任何房间到达，且每个房间最多与 $3$ 扇门相连。 你和你的助手都有描述建筑物内房间相连情况的平面图，但是你们两个各自拥有的平面图虽然描述了相同的房间结构布局，但是房间和门的编号可能不同。 在比赛的第二天，委员会忙于处理赛时通知和选手提问。这将是接近装着奖牌的保险箱的完美机会。 你的助手会首先搜索整栋大楼。一旦他找到保险箱所在的房间，它就会给你留下前往那个房间的提示。由于手机不能带进赛场，他用了去年 BOI 留下的几乎无限供应的领带。由于这些领带完全相同无法区分，你能获得的信息就是他在任何给定房间里所留下的领带数量。由于一个房间内过多的领带非常可疑，因此任何单个房间内领带的最大数量应当尽可能少（参阅评分部分）。 之后，你计划在上厕所的时候溜出去，利用助手留下来的领带找到有保险箱的房间。保险箱藏在房间里，所以你进入带有保险箱的房间时，必须依靠领带识别这个房间；此外，由于“上厕所”时间过长会被发现，你必须尽快找到保险箱。你最多可以走过 $d+30$ 扇门，其中 $d$ 是你的初始位置到保险箱所在位置的最短路径上的门数量。若重复穿过同一扇门，则每次都计入。 因此，你需要编写一个程序，告诉助手需要在每个房间留下多少条领带，并引导你前往带有保险箱的房间。

本题为函数交互题。 对于每个测试点，你的程序会运行两次。 你需要实现如下两个函数（函数原型已给出）： ``` vector<int> mark(vector<pair<int,int>> F, int safe); ``` - $F$: 包含了 $n-1$ 个二元组 $(u,v)$，其中 $1 \le u,v \le n$ 并且保证 $u \neq v$，代表在助手的地图上，$u$ 号房间和 $v$号房间之间由一扇门相连。 - $\mathrm{safe}$: 表示你的助手的地图上保险箱所在的房间编号。 该函数应当返回一个长度为 $n$ 的 `vector<int>` $v$，其中每个元素 $v_i$ 代表你的助手应当在他地图上 $i+1$ 号房间留下的领带数量。你应当保证 $0 \le v_i \le 10^9$。 ``` void locate(vector<pair<int,int>> F,int curr,int t); ``` - $F$: 包含了 $n-1$ 个二元组 $(u,v)$，其中 $1 \le u,v \le n$ 并且保证 $u \neq v$，代表在你的地图上，$u$ 号房间和 $v$号房间之间由一扇门相连。 - $\mathrm{curr}$: 你目前所在的房间编号。 - $t$: 在你当前所处的房间中，找到的领带数量。 在如下的叙述中，房间编号采用你地图的编号方案。 在实现函数 `locate` 的过程中，你可以调用如下函数： ``` int visit(int v); ``` 以此来从你目前所在的房间 $u$ 移动到一个相邻的房间 $v$。你需要保证操作合法，即 $1 \le v \le n,(u,v) \in F\:\vee (v,u) \in F$。 该函数返回一个非负整数 $k$，表示你在房间 $v$ 中找到的领带个数。 该函数调用的次数不应超过 $d+30$，其中 $d$ 是你的起点到终点的最短距离。 当函数 `locate` 终止时，你应当处于带有保险箱的房间内。 对于每个测试点，第一次运行程序时调用 `mark`，第二次调用 `locate`。 如果 `visit` 调用次数过多、调用不合法或在 `mark` 中被调用，你的程序将会被终止运行，提交将会被判**错误**。 你的程序不得写入或读取 `stdin` 或 `stdout`，否则将会被判**违反安全规定**。 但是你可以随便往 `stderr` 输出，没人管这个。 你需要在源代码文件开头加上 `#include "incursion.h"`。 你应当将程序与 `sample_grader.cpp` 链接以进行本地测试。 下面是示例评分器的说明，请参阅 `sample_grader.cpp` 以获取操作说明。 为简单起见，本评分器不会运行你的程序两次，而是在一次运行中调用两个函数各一次。附件中包含了一个 `sample_grader.cpp` 的示例实现。 注意：该实现不与评测所用的实现相同，禁止采用 Hack 评分器的方式试图通过本题！

### 评分细则 共有 4 个 subtask。对于每个测试点，$2 \le n \le 45000$。 Subtask 1 (30 points)，保证没有一个房间有三扇门相连。 Subtask 2 (30 points). 有且仅有一个房间有两扇门相连。 Subtask 3 (40 points). 没有特殊性质。 对于每个测试点，假设使用领带最多的房间用了 $T_{\max}$ 条领带， - $T_{\max}<2$，你将会获得该测试点 $100\%$ 的分数。 - $T_{\max}=2$，你将会获得该测试点 $40\%$ 的分数。 - $2 < T_{\max} \le 10^9$，你将会获得该测试点 $30\%$ 的分数。 ### 交互库使用方法 **注意洛谷提供的交互库与原版不同。** 请使用 `g++ -std=c++17 -Wall -O2 -o test interactive_lib.cpp xxx.cpp` 编译，其中 `xxx.cpp` 是你的程序名字。 示例交互库首先从标准输入读入三个正整数, $n$, $s$, $seed$，表示点数、起点的原编号、随机数种子。 然后读入 $n-1$ 行，每行两个正整数 $u,v$，表示原树的一条边。其中需保证 $1 \le u < v \le n$。 然后读入一行一个字符串，表示打乱规则。 **你不需要在意打乱序号的具体实现。该实现与最终评测所用交互库不一定相同。** 接下来交互库将会调用一次 `mark`，一次 `locate`。注意交互库可能会打乱序号。 交互库可能向终端输出以下信息： - `Invalid input.` 输入不合法。 - `Invalid call to visit. (ALICE CALLED VISIT)` 在 `mark` 中调用 `visit`。 - `Invalid call to visit. (INDEX ERROR)` 访问了不合法的点。 - `Invalid call to visit. (NOT CONNECTED)` 访问的点和当前所在的点没有直接的边相连。 - `Invalid call to visit. (TOO MANY VISITS)` 调用 `visit` 次数过多。 - `Invalid return value of mark.` `mark` 的返回值不合法。即返回的 `vector` 长度不为 $n$ 或者有小于 $0$ 或大于 $10^9$ 的数。 - `Not correct: current position is X` 最终并不在目标点，你应该在 $X$ 点（在第二张地图上）。 - `Correct: at most X tie(s) per room.` 到达目标点，且用领带最多的房间使用了 X 条领带。 最终评测时，只会返回正确与否的信息。