题面
题解
很抱歉的告诉大家，这道题我思考了很长时间，还是不会。
$yyb$代码的细节我也没有弄懂。我知道以后的学习中我会遇到很多这样的题，可能学习方式要进行转变了。
我只能把我看明白的部分讲给大家听。
首先是暴力，我们只要把$trie$树上具有“祖先-后代”关系的点对找出来，然后在他们之间连边，表示它们不能共存。
其次是优化，我们利用$trie$树的形态优化建边。
我们考虑对于每一个点，找到它祖先中所有的点连边（为什么不找到它所有的儿子连边？因为这样的话恐怕是对子树内所有的点连边，暴力的话复杂度就假了，我想的是点内后缀连边，点外$trie$树优化建边），
因为可能$trie$树上的一个位置可能躺着很多点，并且处于复杂度考虑，我们把“真正代表它自己的点”挂在$trie$树中它的位置之下。这样我们连边的时候只需要在$trie$树上找到所有它的祖先的位置，暴力连上去就好了（因为$\sum_{i=1}^{n}{s_i} \le 500000$），所以复杂度是对的。
这样做还有一个问题，我们连边不能连到自己的反，这样的话我们先建一个假点，如果发现要在它上面连边的时候直接建个新点上去，替换它的位置，再让新点向另一棵树中同一个位置的反，表示自己不能到这个点上，在把另一颗树的相同位置连向旧点，表示旧点的值和新点保持一致。这也是要预先排一遍序的原因。
#include<stack> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ri register int #define N 3000300 using namespace std; inline int read() { int ret=0,f=0; char ch=getchar(); while (ch<‘0‘ || ch>‘9‘) f|=(ch==‘-‘),ch=getchar(); while (ch>=‘0‘ && ch<=‘9‘) ret*=10,ret+=(ch-‘0‘),ch=getchar(); return f?-ret:ret; } vector<int> to[N]; inline void add_edge(int u,int v) { to[u].push_back(v); u^=1; v^=1; to[v].push_back(u); } int dfn[N],low[N],clo,bel[N],cnt; stack<int> sta; bool ins[N]; string s[N]; void tarjan(int x) { dfn[x]=low[x]=++clo; sta.push(x); ins[x]=1; for (ri i=0;i<to[x].size();++i) { int y=to[x][i]; if (dfn[y]) { if (ins[y]) low[x]=min(low[x],dfn[y]); } else { tarjan(y); low[x]=min(low[x],low[y]); } } if (low[x]==dfn[x]) { ++cnt; while (1) { int t=sta.top(); sta.pop(); bel[t]=cnt; ins[t]=0; if (t==x) break; } } } int ch[N][2],tot; int n,len[N],id[N]; char ss[N]; void insert(int u,int p) { int x=n+1,lst=0; for (ri i=0;i<len[u];++i) { int c=s[u][i]-‘0‘; if (!ch[x][c]) ch[x][c]=++tot; lst=x; x=ch[x][c]; add_edge(p,x<<1); } int y=++tot; add_edge(p,y<<1|1); add_edge(y<<1,x<<1); ch[lst][s[u][len[u]-1]-‘0‘]=y; } bool cmp(int a,int b) {return len[a]<len[b];} int main() { n=read(); for (ri i=1;i<=n;++i) { scanf("%s",ss); len[i]=strlen(ss); id[i]=i; for (ri j=0;j<len[i];++j) s[i]+=ss[j]; } sort(id+1,id+n+1,cmp); tot=n+1; for (ri i=1;i<=n;++i) { int u=id[i]; for (ri j=0;j<len[u];++j) if (s[u][j]==‘?‘) { s[u][j]=‘0‘; insert(u,u<<1); s[u][j]=‘1‘; insert(u,u<<1|1); break; } else if (j==len[u]-1) { insert(u,u<<1); add_edge(u<<1|1,u<<1); } } for (ri i=1;i<=(tot<<1|1);++i) if (!dfn[i]) tarjan(i); for (ri i=1;i<=tot;++i) if (bel[i<<1]==bel[i<<1|1]) { puts("NO"); return 0; } puts("YES"); return 0; }
原文：https://www.cnblogs.com/shxnb666/p/11373870.html