日志

不存在的……今天偷懒了……只是简单的看了看题目……

stray

感觉这题是个Ad-Hoc题……干就完了！

\(A=3\)的情况

从\(0\)开始作bfs，点\(i\)到\(0\)的距离为\(dis_i\)。

为了讨论方便，不妨设原图是一条链，且\(fa_i\)是\(i\)的前驱。

对于一个点\(u\)，只可能有这几种情况：

1. \(u\)连向\(fa_u\)的。
2. \(u\)连向\(v\)，且\(dis_u\le dis_v\le dis_u+1\)。

因此，我们的染色方案如下：
对于点\(u\ne 0\)，将\((u,f_u)\)染成\(dis_i\bmod 3\)，将其它边染成\((dis_i+1)\bmod 3\)。

显然，对一个节点，它的边只可能有两种颜色。

我们的遍历方案如下：
对于一次Move，若只有一种颜色，则其只可能为惟一的\((u,fa_u)\)，沿着它走即可。
否则，找较“前”的一种颜色，沿着它走即可。

\(A=2\)的情况

原图是一棵树，且最多允许走错\(3\)步。

我们先来考虑它的一个子问题：没有点的度数\(=2\)的情况。

此时，可以按之前的方法染色，选取出现次数较少的边即可。

我们再考虑它的一个子问题：原图是一条链的情况。

此时，按之前的方式染色是行不通的，但是我们注意到此时的\(B\ne 0\)，只需要按照一种能够区分上下方向的方式染色即可。

我们考虑按照\(1,1,0,0,1,0,\dots\)这样循环染色。如果是向上的，则应该读出来是\(1,1,0,1,0,0\)，可以区分！

我们可以进一步发现，这种方式可以通过\(B=6\)的子任务：

1. 若最开始在两个\(1\)中间，可以在三步内得知当前的方向（\(1,1,0,0\)与\(1,1,0,1\)）。
2. 若最开始在一个\(1\)和一个\(0\)中间，也同理（\(1,0,1\)与\(1,0,0\)）。

实际上，只需要随便走三步，然后

我们把这两个思路合在一起：对于一个点\(u\ne 0\)，若它的度数为\(2\)，则按照\(110010\)周期染色，否则按照深度染色。可以通过循环移位使得两个条件都满足。

实际上，只考虑长度为\(4\)的子串是完全不够的。然而神仙的zbw爷爷打了个补丁：只需要知道一个长度为\(5\)的子串就够了……然而，你可以走到第\(4\)个点时，不急着走，此时你可以获取一个\(5\)条边的序列！！可以通过在两倍\(110010\)上爆搜来知晓当前的方向。

%%%zbwyy tql