某科学的超现实树

Spasmodic · 2022-04-04 21:58:58 · 题解

尝试提供一个结论不那么突兀的题解。下简称几乎完备的集合为 AC 集合（Almost Complete）。

定义映射 l(\mathscr T) 表示将集合 \mathscr T 中的树全部替换为其左子树，r(\mathscr T) 同理。

• 我们考察一个 AC 集合 \mathscr T，希望找出一些二叉树，使得它们满足如下条件：
  • 有无限个
  • 任意去掉有限个后都几乎完备
  • 方便我们处理
• 考虑左子树或右子树大小不超过 1 的树，这些树可以生长得出其他的树，且有无穷多个，满足上面的要求。
• 我们先考察左子树为空的树，这样的树只能由一颗左子树也为空的树生长得出。考察 \mathscr T 中一切满足这样条件的树构成的集合 \mathscr S_{l0}，那么有 r(\mathscr S_{l0}) 是 AC 集合。
• 同理，我们分别考虑左子树为孤立点，右子树为空，右子树为孤立点的集合，可以发现 r(\mathscr S_{l1}),l(\mathscr S_{r0}),l(\mathscr S_{r1}) 也都是 AC 集合。这样，我们可以得到一个必要条件。
• 这个条件是否充要呢？考察其逆命题，任取一树，如果其不属于 \operatorname{grow}(\mathscr T)，则其左子树选择有限，右子树选择有限（不然可以分别由 \mathscr {S_{r0}/S_{r1},S_{l0}/S_{l1}} 生长出），因此 \mathscr T 也 AC！
• 推出这个条件后，我们顺带可以推出一个推论：我们发现对于 \mathscr T 中的树，如果其左子树和右子树的大小都大于 1，那么根据充要条件，这颗树是没有贡献的。考虑递归过程，我们意识到，对任意一个节点，如果其左子树和右子树的大小都大于 1，那么这颗树都是没有贡献的，因为当我们递归到这个点，它就会被抛弃掉。

推到这里，形式就明朗了不少：我们首先去掉多余的树，然后递归判定 \mathscr {S_{r0},S_{r1},S_{l0},S_{l1}} 是否都 AC 即可。

ix35 说这样直接实现就可以了，但是我觉得不太好写，下面提供一个较好的实现方法：

我们观察到对于每一颗树，它每次被划分到 \mathscr {S_{r0},S_{r1},S_{l0},S_{l1}} 哪一个与其他树无关，我们可以提前划好，此时就找到了一个 dfs 树上根到叶子的链。当然，在末尾处有可能会出现同时被分到 \mathscr S_{r1} 与 \mathscr S_{l1} 的情况，那么我们就视为两条不同的链插入。

我们把划分结果视为字符 0/1/2/3，链视为字符串，我们发现：本质上这是一颗 Trie 树！每次我们输入一颗树后，就可以在线地转化为字符串插入到 Trie 树里。当然，与普通的 Trie 树还有一定区别：当我们插入到一个字符串的终止节点时，我们发现对应在 dfs 树上就是发现集合中存在孤立点，这种情况显然是 AC 集合，因此不用继续插入，可以直接退出。

最后怎么判断有解？很简单，只要判断每个非终止节点的点的出度都是 4 即可，如果不是，那么在 dfs 到此处时就会发现存在一个 \mathscr S=\varnothing，显然是无解的。

时间和空间复杂度都是 O(\sum n)。

const int N=2e6+5;
int T,m,n,trie[N<<1][4],rt,cnt,lc[N],rc[N];
bool ed[N<<1];
void build(int u,int&p){
    if(!p)p=++cnt,ed[p]=0,trie[p][0]=trie[p][1]=trie[p][2]=trie[p][3]=0;
    if(ed[p])return;
    if(!lc[u]&&!rc[u]){ed[p]=1;return;}
    if(!lc[u])return build(rc[u],trie[p][0]);
    if(!rc[u])return build(lc[u],trie[p][1]);
    if(!lc[lc[u]]&&!rc[lc[u]])build(rc[u],trie[p][2]);
    if(!lc[rc[u]]&&!rc[rc[u]])build(lc[u],trie[p][3]);
}
bool ok(int p){
    if(!p)return 0;
    if(ed[p])return 1;
    rep(i,0,3)if(!ok(trie[p][i]))return 0;
    return 1;
}
int main(){
    for(IO>>T;T--;){
        for(IO>>m,cnt=rt=0;m--;){
            IO>>n;
            rep(i,1,n)IO>>lc[i]>>rc[i];
            bool flag=1;
            rep(i,1,n)
                if(lc[i]&&rc[i]&&(lc[lc[i]]||rc[lc[i]])&&(lc[rc[i]]||rc[rc[i]]))flag=0;
            if(!flag)continue;
            build(1,rt);
        }
        if(ok(rt))puts("Almost Complete");
        else puts("No");
    }
    return 0;
}