题目背景

译自 9th Romanian Master of Informatics, 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 函数。

你需要实现以下的函数：

void assignHints(int subtask, int N, int A[], int B[]);
void speedrun(int subtask, int N, int start);

你可以调用以下的函数：

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$		菊花图		$8$
$3$			链		$19$
$4$	$316$	$32\, 000$			$12$
$5$	$40$	$2\, 000$		II	$40$

• 菊花图：存在一个度数为 $(N-1)$ 的节点。
• 链：每个节点度数均不大于 $2$。
• 计分方式 $\text{I}$：成功遍历树，得满分；否则得 $0$ 分。
• 计分方式 $\text{II}$：成功遍历树的得分为 $\min(40,60-l)$。