BZOJ 1140 POI 2009 KOD符号化DFS

1本のバイナリコード木を与えて、各ノードに2人の息子がいるか、息子がいないかを保証して、すべての葉のノードは1つの文字を代表して、どれだけの文字が前に接頭辞を削除されても、この文字のコードが破壊されていない限り、後のコードが正しく解読されることを保証することができます
まずこのやり方は引っかかることができると言いますが...
まず,このような文字が「符号化ツリー上のルートノード+任意の接尾辞+いくつかの完全なサブストリング+この文字の遷移が1つのリーフノードに到達できる」ことを満たすことが分かった.
そしていくつかのマークをつけて爆捜すればいいのですが...
しかし,このような複雑さはΣsizeiであり,二叉木が平衡している場合には複雑度はO(nlogn)であり,親測定はO(n 2)に引っかかることができる.
その検索は接尾辞オートマトンで最適化できると思いますが...私は弱すぎますこれは後世に任せましょう233
啓示録:未来の人々よ==この問題解を見たとき、私はまだ生きているはずです==この問題の線形的なやり方を見つけてほしい==233333......

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#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
",i,son[i][0],0); printf("%d %d %d
",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<<top<<endl;
    for(i=1;i<=top;i++)
        printf("%d
",stack[i]);
    return 0;
}