P6776 [NOI2020] 超现实树

\(\mathcal {Link}\)

比较智慧，但如果能想到链树的话其实不难。（为啥全机房都在刷 Ynoi 就我在搞思维题啊）

考虑啥叫“只有有限棵树不能被表示出来”。可以发现，这等价于任意一棵深度无穷的树都能够被表示。

据此，考虑简化无穷树集，若无穷深度树 \(T'\) 能被 \(T\) 表示，那我们只考虑 \(T\) 即可。

由于是无穷深度树，考虑只保留一条无穷深度链，其它全部变为单点。这种树称为链树。

显然，所有无穷深度树属于 \(\operatorname{grow}(\mathscr T) \iff\) 所有无穷深度链树属于 \(\operatorname{grow}(\mathscr T)\)

分析链树的性质。可以发现，任何一个节点左右子树大小的较小值不超过 \(1\)。

然后你会发现，非链树无法生成链树，所以非链树无用。

至于判定，非常简单。

将链树分为五类：

• 单点
• 无左子树
• 无右子树
• 左子树为单点
• 右子树为单点

第一种直接返回，后四种继续递归。

复杂度：不会算，大概是 \(\mathcal O(\sum n)\) 的？

具体写法的话，考虑建出类似的递归树，每层四个节点，分别对应四种情况。

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
using ll=long long;
char buf[1<<14],*p1=buf,*p2=buf;
#define GetC() ((p1==p2)&&(p2=(p1=buf)+fread(buf,1,1<<14,stdin),p1==p2)?EOF:*p1++)
struct Ios{}io;
template <typename _tp>
Ios &operator >>(Ios &in,_tp &x){
    x=0;int w=0;char c=getchar();
    for(;!isdigit(c);w|=c=='-',c=getchar());
    for(;isdigit(c);x=x*10+(c^'0'),c=getchar());
    if(w) x=-x;
    return in;
}
const int N=2e6+5;
int ls[N],rs[N];
int son[N];
bool check(int u){
    son[u]=1;
    bool flag=true;
    if(ls[u]) flag&=check(ls[u]),son[u]+=son[ls[u]];
    if(rs[u]) flag&=check(rs[u]),son[u]+=son[rs[u]];
    flag&=min(son[ls[u]],son[rs[u]])<=1;
    return flag;
}
int cnt;
bool is[N];
int ch[N][4];
int rt;
void dfs(int u,int &x){// u:cur_tree x:tot_tree
    if(!x) x=++cnt;
    if(!ls[u]&&!rs[u]){
        is[x]=true;
        return ;
    }
    if(!ls[u]) dfs(rs[u],ch[x][0]);
    if(!rs[u]) dfs(ls[u],ch[x][1]);
    if(son[ls[u]]==1&&rs[u]) dfs(rs[u],ch[x][2]);
    if(son[rs[u]]==1&&ls[u]) dfs(ls[u],ch[x][3]);
}
bool check_ans(int u){
    if(!u) return false;
    if(is[u]) return true;
    return check_ans(ch[u][0])&&check_ans(ch[u][1])&&check_ans(ch[u][2])&&check_ans(ch[u][3]);
}
int main(){
    int T;io>>T;
    while(T--){
        cnt=0;
        int m;io>>m;
        rt=0;
        for(int i=1;i<=m;++i){
            int n;io>>n;
            for(int i=1;i<=n;++i) io>>ls[i]>>rs[i];
            if(!check(1)) continue;
            dfs(1,rt);
        }
        if(check_ans(rt)) puts("Almost Complete");
        else puts("No");
        for(int i=1;i<=cnt;++i) is[i]=false,ch[i][0]=ch[i][1]=ch[i][2]=ch[i][3]=0;
    }
    return 0;
}

最后只需要穿上去就好了。