CF gym 101190B Binary code:
题目大意：
有 \(n\) 个最多一位未定的 01 字符串，现在请你输出一种方案，表示构造一种填 0/1 的方案。
使得不存在两个字符串一个是另一个的前缀，不存在输出 \(no\)。
\(n \le 5 \times 10^5\)。
解题思路：
两个串一个为另一个的前缀的很好的判定方式就是一个串在另一个串的 \(Trie\) 子树内。
也就是说我们要建出一棵 01 \(Trie\) 使得字符串对应的节点两两没有祖先关系。
由于每个串最多两种情况，那么我们可以将每种情况都先加到 \(Trie\) 树中。
那么相当于对于每一对有祖先关系的节点都只能选一个。考虑 \(2-sat\)。
有一种很精妙的实现方法，就是在递归 Trie 树时记录一个节点表示该点祖先中至少选一个的 ”超级点“。
可以这样是因为我们只关心他不能与祖先有关系，所以我们可以将祖先看成一个整体。
\(O(n)\)。
但这么做我觉得扩展不到线段树优化建图上，因为 Trie 每个节点都是一个具体的节点，但线段树一般不会存祖先，如果存的话就得爆了。
不过线段树的应用范围还是更广的，因为即使是这个题也可以将 Trie 拍成 dfn 序，这样在 dfn 序上线段树优化建图多个 log。