题目大意
给定一幅 $n$ 个点 $m$ 条边的 DAG。你有三种颜色（红蓝绿），你要给每条边染色，使得不存在一条路径上连续 42 条边同色。
$n \leq 50000,\ m \leq 2 \times 10^5$
naive想法1
今天的主题是 random algorithm，于是下午的 contest 就变成了随机大战+乱搞大战。于是这题理所当然地首先想想随机。
似乎直接给每条边随机一个颜色很优秀啊？你想想，一条路径连续 42 个同色的概率不是几乎为 0 吗？
然而非常好叉，因为这不是随机图，只要让两个点之间重边非常多，那么在随机下每个点到另一个点什么颜色都有了，轻松 42 条同色。
然后又脑洞了一下：给每个点随机一种颜色然后这个点的出边全都是这种颜色、按 bfs 序每15层全部同色轮换然后其他随机……全都 WA 了。然后发现，只要把点分层，每层 100 个，共 500 层，相邻两层之间完全相连，不同层之间再随便加些边扰动一下，那么在随机下每层到下一层也是什么颜色都有，依然轻松 42 条同色。
因此本质问题是，上面这种数据就是卡掉所有随机的。思考的方向不是让它如何更随机，因为越随机，这种数据越过不去。应该构造一种方案使得它在这种情况下不那么随机。
因此这是一个构造题。
naive想法2
需要构造一种方法，使得如果连续 42 条边同色的话，会有什么东西爆掉。比如让点的编号爆掉。
有一种很 naive 的想法是，设 $x$ 的二进制最高位的 1 是从右往左数第 $w_x$ 位，比如 $i$ 连向 $j$，若 $i < j$，且 $w_i < w_j$，那么 $i$ 到 $j$ 连红边。这样的话，红边连续意味着二进制最高位的 1 一直向前推进，那么连续 42 次编号肯定爆了。然后比如当 $w_i > w_j$ 时连绿边，那么连续 42 条绿边也爆了……
但是还有很多情况没考虑，比如 $w_i=w_j$ 怎么连……会发现三种颜色不太够，因此方法要改进一下。
基于这种思路就得出了一种构造方法。
首先为了去掉 $i > j$ 的情况，我们用拓扑序编号来做。对于 $i$ 连向 $j$，设它们的拓扑序编号分别为 $id_i$ 和 $id_j$，那么一定有 $id_i < id_j$。
然后我们不要讨论最高位的 1，而是讨论 $id_i$ 和 $id_j$ 二进制下第一个不同的位，即 $w_{id_i \oplus id_j}$。由于 $n \leq 50000$，因此 $id$ 二进制最多只有 16 位，那么我们对 $w_{id_i \oplus id_j}$ 进行讨论：若为 $1$~$5$，连红边；若为 $6$~$10$，连绿边；若为 $11$~$16$，连蓝边。这样红边和绿边的连续转移都不超过 $2^5=32$ 次。蓝边因为有第 16 位，严格分析一下最大是 $48$ 次。
比赛时脑子抽了以为蓝边也是 32 次，于是勇敢地写了，然后过了。。。
估计出题人也没想过我这种偏门的想法于是没有专门出数据去卡。。。
直到写这个 blog 重新证明一次才发现被叉掉了 qaq
不过这场本身也是乱搞大战，我乱搞过了这个题不也算是正解吗（大雾
（当然还是希望有 dalao 继续完善一下这个想法。
题解
然后题解异常地简单，思路很直接。（其实是因为我想的太复杂了qaq
先对点进行分组，分成 $42$ 个组，每组 $\frac{n}{42}$ 个点。组与组之间的转移连红边。由于是 DAG，红边连续最多 41 次。
对于每组内，再分 $42$ 个小组，每小组 $\frac{n}{42 \cdot 42}$ 个点。小组与小组之间转移连蓝边。同理，蓝边连续最多 41 次。
由于小组内点数 $\frac{n}{42 \cdot 42} < 42$，因此小组内转移连绿边。这样绿边连续也不超过 42 次了。
这个方法用的思想是 $42^3>n$，因此连续分组两次就行了。
代码
// naive想法2
1 |
|