P6776 [NOI2020]超现实树解题报告

解题报告

P6776 [NOI2020]超现实树解题报告：

更好的阅读体验

题意

• 定义一棵树的替换为将其任意一个叶子结点替换为任意一棵树之后形成的树；
• 定义$grow(\mathscr{T})$为里面所有树进行任意步替换能构成的树的集合；
• 定义一个$grow$集合完备当且仅当仅存在有限棵树不存在于这个集合中；
• 给定一个$m$棵树组成的森林$\mathscr{T}$，判断$grow(\mathscr{T})$是否完备。
• 多组数据，$\sum n\leqslant 2\times 10^6$。

分析

神仙题，同步赛的时候只想到了讨论儿子的情况，但是由于没想到只有链树可以对答案贡献，因此发现讨论不出来情况，最后只拿了$40pts$。

定义：我们定义链树为一条链上每个节点挂或不挂一个叶子结点形成的树。

引理$1$：任意非链树的数无法通过替换得到链树

证明：替换操作不会删除任意原有的结点，因此新生成的树依旧无法满足链树的条件。

引理$2$：$grow(\mathscr{T})$的完备性等价于只有有限棵链树不被$grow(\mathscr{T})$包含。

证明：

• 充分性：如果无数棵链树不在$grow(\mathscr{T})$中，那么肯定有无限棵树不在$grow(\mathscr{T})$中；
• 必要性：如果无数棵树不在$grow(\mathscr{T})$中，那么我们一定有无限个深度不相同的树不在$grow(\mathscr{T})$中，对于每一个深度的树我们都可以砍去一些子树使得这棵树变为链树，显然这棵链树也无法替换而成。（如果可以替换而成，那么一定可以生成这颗不包含在$grow(\mathscr{T})$中的树）

引理$3$：只有链树可以对$grow(\mathscr{T})$的完备性产生影响。

证明：由于引理$1$，我们知道任意一颗不是链树的树一定无法替换成链树，而由引理$2$得我们只关心链树是否可以被替换而成，因此我们只需要链树。

这样，我们的任务就转化为了能否用给定的所有链树替换出无限的链树。（注意：下文中$\mathscr{T}$集合专指剔除了非链树的给定树集合）

首先，我们要判断链树（$\text{check}$函数）：

int isleaf(int x){
    return x!=0&&ls[x]==0&&rs[x]==0;
}
int check(int x){
    if(x==0||isleaf(x))
        return 1;
    return (check(ls[x])==0&&check(rs[x])==0)? 0:1;
}

对于链树上的结点，它儿子的情况只有四种：①只有左儿子②只有右儿子③有左右儿子，但是有一个儿子是叶子结点（根据链树的定义很显然有这一点）。

因此我们也可以很快写出来链树的合并：

void merge(int &now,int x){
    if(now==0)
        now=++cnt;  
    if(isleaf(x)){
        ok[now]=1;
        return ;
    }
    if(isleaf(ls[x])&&isleaf(rs[x])){
        merge(chd[now][2],ls[x]),merge(chd[now][3],rs[x]);
        return ;
    }
    if(ls[x]==0)
        merge(chd[now][1],rs[x]);
    if(rs[x]==0)
        merge(chd[now][0],ls[x]);
    if(rs[x]&&isleaf(ls[x]))
        merge(chd[now][3],rs[x]);
    if(ls[x]&&isleaf(rs[x]))
        merge(chd[now][2],ls[x]);
}

定义结点$x$为好点当且仅当只存在有限棵树不能被$x$的子树替换出来，好点的判断可以通过一种递归的方式写出：

int grow(int x){
    if(x==0)//不存在这个点
        return 0;
    if(ok[x]==1)//解释见下
        return 1;
    return grow(chd[x][0])&&grow(chd[x][1])&&grow(chd[x][2])&&grow(chd[x][3]);
    //chd[x][0/1/2/3]为x儿子的四种情况
}

解释：某个子树可以替换出来它子树所有情况只有两种情况：要么是给定的链树集合$grow(\mathscr{T})$存在一棵树让这个位置的结点为叶子结点（这样一定可以替换出所有的树），要么是这个点所有的儿子都是好点。

这样我们只需要判断根结点是否为好点就可以了。

代码

代码&压行后的代码