CF1007D Ants

题意：有一颗 个点的树。

给出 个染色要求 ，第 个要求形为 ：

路径 或者 上的边全染成颜色 。

构造一组方案或指出无解。

，，时限 ，空限 。

---

我们用点来代表返祖边，转化为点的染色。

将每个染色要求视为一个变量，则同一只蚂蚁的两个染色要求必须满足其中一个，不难发现这是个 2-SAT 问题。

此外，对于有交集的两条（异色）染色要求，还需要求两者不能同时为真。

---

数据结构优化建边。

先把树重链剖分，将树上的一条路径拆分到 个线段树节点上。

观察可以发现，和线段树上一个节点有交集的其他节点是：祖先和子树。

那么，在线段树上从上到下，从下到上分别处理对祖先和子树的连边。

在同个点中，还要与所有其他异色变量连边。

这可以预处理前缀后缀然后拼起来（恰好略过自己）完成。

时空复杂度 。

十分难写。