题解 P6776 【[NOI2020]超现实树】

· · 题解

题意

定义树 T^{\prime} 能被树 T 单步替换得来，当且仅当将 T 的某个叶子替换成一棵二叉树之后与 T^{\prime} 同构，记作 T\leadsto T^{\prime}。

定义树 T^{\prime} 能被树 T 生成当且仅当单步替换链 T\leadsto T_1\leadsto\cdots\leadsto T_n 存在，记作 T\to T^{\prime}。同时记 \text{grow}(T)=\{T^{\prime}\mid T\to T^{\prime}\}。

对于若干二叉树组成的集合 \mathscr{T} 来说，定义 \text{grow}(\mathscr{T}) 为：

\text{grow}(\mathscr{T})=\bigcup\limits_{T\in\mathscr{T}}\text{grow}(T) $\texttt{Data Range:}\sum n\leq 2\times 10^6

题解

此题牛逼！

记 h(T) 表示 T 的高度，定义 B_n 表示高度为 n 的所有二叉树的基底。B_n 中的树 T 需要满足以下两个条件：

比如说，B_2 由以下三棵树组成：仅有根节点和左子树的，仅有根节点和右子树的，根节点和两个子树都有的。

多手玩几个你会发现属于 B_n 的树有一个共同的特点：由一条长度为 n 的链和一些附着在链上的单个节点所组成，我们把这种树叫做链树。

现在我们证明这些 B_n 内的所有链树一定能够生成出所有高度为 n 的树。对于每一棵高度为 n 的树 T 而言都会有一条长度为 n 且从根节点往下的链，这个时候我们让 T^{\prime} 也拥有这条链。对于 T 中链上的非叶节点来说，有一个儿子在链上，如果另一边没有儿子则不操作，否则将 T^{\prime} 对应的位置加入一个叶子。很明显 T^{\prime} 为链树且 T^{\prime}\to T。一个例子可以参考下图。

很明显，上面那棵树中有链 1\to 2\to 6，所以将其保留下来。对于 1 来说，非链的另一侧子树（也即以 3 为根的子树）非空，所以新树中只留下 1 的直接儿子 3，对于 2 来说也一样，最终得到下面的树。

同时可以证明 B_n 中的任意一棵树不能生成其他树，这个很简单。

注意到一个性质：对于 u>v 来说，B_u\subseteq \text{grow}(B_v)。翻译成人话也就是所有高度为 u 的链树能被所有高度为 v 的链树生成。

不仅如此，还有一个性质是非链树不可以生成链树，因为生成操作不会导致树的基础形态改变。这也就意味着一堆非链树组成的集合一定是不完备的，相当于非链树答案没有影响。依靠这三个性质，我们可以证明只有所有链树是有用的。（也即非链树不能生成链树，而链树可以生成更高的链树从而生成更高的非链树）

现在我们将所有 \mathscr{T} 内的非链树剔除掉，并且将所有链树合并。对于链树上的一个非叶节点 u，存在四种情况：

对于上图链树中的 2 我们认为同时满足后两种情况。将这些情况编码为 0,1,2,3，就可以用一棵四叉树来表示所有链树了。

我们定义四叉树上的节点 u 是完备的当且仅当只有有限棵树不能被 u 子树生成，那么很明显 u 是完备的必须满足下面两个条件之一：

这个可以简单搜一下，最后只要看根节点是否是完备的即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long long int li;
const ll MAXN=2e6+51;
ll test,n,m,totn,rt;
ll ls[MAXN],rs[MAXN],c[MAXN],ch[MAXN][4];
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
}
inline ll chk(ll x)
{
    return !ls[x]&&!rs[x];
}
inline ll check(ll x)
{
    if(chk(x)||(!ls[x]&&check(rs[x]))||(!rs[x]&&check(ls[x])))
    {
        return 1;
    }
    return (chk(ls[x])&&check(rs[x]))||(chk(rs[x])&&check(ls[x]));
}
inline void merge(ll &cur,ll x)
{
    !cur?cur=++totn:1;
    if(chk(x))
    {
        return (void)(c[cur]=1);
    }
    !rs[x]?merge(ch[cur][0],ls[x]):(void)1;
    !ls[x]?merge(ch[cur][1],rs[x]):(void)1;
    ls[x]&&rs[x]&&chk(rs[x])?merge(ch[cur][2],ls[x]):(void)1;
    ls[x]&&rs[x]&&chk(ls[x])?merge(ch[cur][3],rs[x]):(void)1;
}
inline ll grow(ll x)
{
    if(!x||c[x])
    {
        return !!x;
    }
    return grow(ch[x][0])&&grow(ch[x][1])&&grow(ch[x][2])&&grow(ch[x][3]);
}
inline void solve()
{
    n=read(),rt=totn=0;
    for(register int i=1;i<=n;i++)
    {
        m=read();
        for(register int j=1;j<=m;j++)
        {
            ls[j]=read(),rs[j]=read();
        }
        check(1)?merge(rt,1):(void)1;
    }
    puts(grow(1)?"Almost Complete":"No");
    for(register int i=1;i<=totn;i++)
    {
        ch[i][0]=ch[i][1]=ch[i][2]=ch[i][3]=c[i]=0;
    }
}
int main()
{
    test=read();
    for(register int i=0;i<test;i++)
    {
        solve();
    }
}