图论

给定一个 $n$ 个点的竞赛图，给该图的每条边染色，颜色数量不能超过 $m$ 个，一个染色合法当且仅当不存在长度为 $2$ 的路径，即对有向图中任意路径 $i \rightarrow j \rightarrow k$ 均有边 $i \rightarrow j$ 和边 $j \rightarrow k$ 颜色不同 $2 \le n \le 3000, ~ 2 \le m \le 26$ 设该竞赛图点集 $V$ 考虑染每一种颜色意味着什么，相当于选择一个点集 $S \subseteq V$，将所有边 $(u, v)$ 满足 $u \in S \cap v \in \complement_VS$ 染上该颜色，也就是说我们要找到至多 $m$ 个这样的集合来覆盖所有的边 这样可以给出一个 $m = 2\log n$ 的染色方案，对所有点分治，每次一分为二，给 $S, \complement_V S$ 之间的边按两种方向染上不同的颜色，这样总共需要颜色是 $2\log n$ 的 但实际上可以用二进制来表示这种是否在每个 $S$ 中的关系，对每个 $S_i$，若当前点 $u$ 得到的二进制位 ...