题意简述

判定 n 个含 ? 字符的二进制串是否存在一种把 0/1 填入 ? 中的方案使得任意两个串不具有前缀关系。

(一个串最多一个 ?)

Sol

二进制串 ，并且一个串最多一个 '?'

很容易想到用 2-sat 和 trie 树。

那么问题变为插入这些二进制串，在 ‘?’ 处选择向哪边插入 ，使得任意一个结束节点的祖先节点中不存在一个结束节点。

然后我们考虑构建 2-sat 模型，首先每一个串分配一个变量表示 '?' 选择了什么(没有?就随便强制选则某一个就行了)

当然之后我们一种思路是直接用这些变量来判定并解决问题 ，不过复杂度显然是 \(O(n^2)\) 的。

考虑优化，因为是祖先中不能存在结束节点，我们给每一个 trie 树上的节点加一个变量表示除去自己外的祖先中是否存在结束节点，这个东西显然从上到下具有传递性，那么可以初步建图了。

然后看怎么体现一个串的 '?' 的决策情况。发现这个东西不是很好做，因为结束节点不会受到自己影响。那么我们直接新建一个变量好了，表示包含了当前位置的情况下祖先是否有结束节点。

之后我们还需要解决一个问题，就是一些不同的串可能共用了结束位置，我们显然不能够让他们共用一个变量，因为他们之间也是互相影响的，并且他们还来自不同的 '?' ，不能共用。

发现这个东西可以直接和上面的情况合并到一个变量上，因为本来我们插入完之后就要新建一个点，那么正好一起用，也不影响答案，把该连的边连上就行了。

code：

#include
    
     using namespace std;template
     
      inline void init(T&x){    x=0;char ch=getchar();bool t=0;    for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') t=1;    for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch-48);    if(t) x=-x;return;}#define TR(a) ((a)<<1|1)#define FA(a) ((a)<<1)const int N=5e5+10;const int MAXN=3e6+10;int son[MAXN][2];char S[N];char *s[N];int len[N],id[N];int n,cnt=0;inline bool cmp(int i,int j){return len[i]
      
       len[t]) {add(TR(t),FA(t));Insert(s[t],len[t],FA(t));}    }    for(int i=0;i<=cnt;++i) if(!dfn[i]) tarjan(i);    puts("YES");    return 0;}