题目大意：给定一棵二进制编码树，保证每个节点要么有2个儿子，要么没有儿子，每个叶节点代表一个字符，求有多少字符满足即使前面被删掉一个前缀，只要这个字符的编码没有被破坏，就可以保证后面的编码都解读正确

先说下这个做法是可以被卡的……

首先我们可以发现这样的字符满足【编码树上根节点+任意一个后缀+一些完整的子串+这个字符的转移都能到达一个叶节点】

然后打几个标记爆搜就行了……

然而这样做的复杂度是 ∑sizei 的，当二叉树很平衡的时候复杂度是 O(nlogn) ，亲测可以卡到 O(n2)

我觉得那个搜索可以用后缀自动机来优化一下……然而我太弱了
这个就交给后人吧233

启示录：
未来的人们啊= =
当你们看到这篇题解的时候，我应该还活着= =
希望你们能够找到这道题的线性做法= =
233333……

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #define M 1200100 using namespace std; int n,tot; int son[M][2]; char s[3003003]; int stack[M],top; int a[M]; bool v1[M],v2[M],not_ans[M]; void DFS1(int p1,int p2) { if(!son[p2][0]) { if(!v1[p1]) v1[p1]=true,stack[++top]=p1; return ; } if(!son[p1][0]) return ; DFS1(son[p1][0],son[p2][0]); DFS1(son[p1][1],son[p2][1]); } void DFS2(int p1,int p2) { if(!son[p2][0]) { if(!v2[p1]) v2[p1]=true,p2=1; else return ; } if(!son[p1][0]) { if(p2!=1) not_ans[p1]=true; if(!v1[p2]) v1[p2]=true,DFS2(1,p2); return ; } DFS2(son[p1][0],son[p2][0]); DFS2(son[p1][1],son[p2][1]); } int main() { int i; cin>>n; scanf("%s",s+1); stack[++top]=++tot; for(i=1;i<=n;i++) { switch(s[i]) { case '0': son[stack[top]][0]=++tot; stack[++top]=tot; break; case '1': son[stack[top]][1]=++tot; stack[++top]=tot; break; case 'X': a[++a[0]]=stack[top]; break; case 'B': stack[top--]=0; break; } } /* for(i=1;i<=tot;i++) if(son[i][0]) { printf("%d %d %d\n",i,son[i][0],0); printf("%d %d %d\n",i,son[i][1],1); } */ for(i=2;i<=tot;i++) DFS1(1,i); while(top) DFS2(1,stack[top--]); for(i=1;i<=a[0];i++) if(!not_ans[a[i]]) stack[++top]=i; cout<