P11315 [RMI 2021] 速通 / Speedrun

译自 [9th Romanian Master of Informatics, RMI 2021](https://rmi.lbi.ro/rmi_2021/) D1T3。$\texttt{3.5s,0.5G}$。 评测时，**不要引入头文件**。在文件头加入如下的语句： ``` void setHintLen(int); void setHint(int,int, bool); int getLength(); bool getHint(int); bool goTo(int); ```

**这是一道通信题。** 你在一棵 $N$ 个节点的树上，从某个节点出发跑酷。 **你不知道这棵树的具体形态**，只知道现在自己在哪个节点。你在点 $u$ 时，唯一能做的就是选择一个 $v$，尝试走到 $v$。如果 $(u,v)$ 这条边存在，你会走到 $v$；否则你将留在原地。 需要注意的是，**你最多能试错 $Q$ 次**。也就是说，如果你超过 $Q$ 次选择了一条不存在的边，就失败了。 当你经过每个节点至少一次时，我们说你**速通成功**。 现在有一个作弊的机会。你可以在每个节点放一个长度为 $l$ 的 $\texttt{01}$ 串，当你在某个节点时，可以读取那个节点上 $\texttt{01}$ 串的信息。需要注意的是，在放置 $\texttt{01}$ 串的时候**你是知道这棵树的形态的，但是你不知道自己跑酷时的出发点。** 请你找到一种设置信息和速通的方式，使得速通成功。 ### 实现细节 你不需要，也不应该实现 main 函数。 你需要实现以下的函数： ```cpp void assignHints(int subtask, int N, int A[], int B[]); void speedrun(int subtask, int N, int start); ``` 你可以调用以下的函数： ```cpp void setHintLen(int l); void setHint(int i, int j, bool b); int getLength(); bool getHint(int j); bool goTo(int x); ``` #### 第一次运行 第一次运行用于确定每个节点上的信息。 交互库将会调用 `assignHints` 函数恰好一次。参数的含义： - `subtask`：子任务编号。 - `N`：树的节点数量。 - `A[]`, `B[]`：长度为 $N$ 的整数数组，含义为对于每个 $i=1,2,\cdots, N-1$，$A[i],B[i]$ 间有一条边连接。 随后，你需要立刻调用 `setHintLen` 函数恰好一次。传入正整数 `l` 表示你的 $\texttt{01}$ 串的长度。 $\texttt{01}$ 串起初全为 $0$。 接下来，你可以多次调用 `setHint`，其中 $1\le j\le l$，表示将节点 $i$ 的 $\texttt{01}$ 串的第 $j$ 位设置成 `b`。 在第一次运行中，禁止调用 `getLength`，`getHint` 和 `goTo`。 #### 第二次运行 交互库将会调用 `speedrun` 函数恰好一次。参数的含义： - `subtask`：子任务编号。 - `N`：树的节点数量。 - `start`：你的初始位置。 调用 `getLength` 来获得 $\texttt{01}$ 串的长度。 当你在节点 $i$ 时，调用 `getHint(j)` 来获得当前节点上 $\texttt{01}$ 串的第 $j$ 位。 可以调用 `goTo` 来尝试移动一步。如果成功，返回值为 `true`；否则返回值为 `false`。 在第二次运行中，禁止调用 `setHint` 和 `setHintLen`。

无

无

对于 $100\%$ 的数据，保证 $1\le N\le 10^3$。 令 $Q$ 为 `goTo` 函数返回 `False` 的最大次数，$L$ 为 $l$ 的最大值。超出限制，得 $0$ 分。 | 子任务编号 | $L\le $ | $Q\le$ | 树的形态 | 计分方式 | 得分 | | :--: | :--: | :--: | :--: |:--: | :--: | | $ 1 $ | $ N $ | $2\,000$ | | I | $21$ | | $ 2 $ | $ 20 $ | $2\,000$ | 菊花图 | I | $8$ | | $ 3 $ | $ 20 $ | $2\,000$ | 链 | I | $19$ | | $ 4 $ | $ 316 $ | $32\, 000$ | | I |$12$ | | $ 5 $ | $ 40 $ | $2\, 000$ | | II | $40$ | - 菊花图：存在一个度数为 $(N-1)$ 的节点。 - 链：每个节点度数均不大于 $2$。 - 计分方式 $\text{I}$：成功遍历树，得满分；否则得 $0$ 分。 - 计分方式 $\text{II}$：成功遍历树的得分为 $\min(40,60-l)$。