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

· · 题解

学文化课之前分享一下自己的方法和代码留作纪念。

我们需要求\ grow(T)是否是几乎完备的。

说一下为了方便而下的定义：

我们考虑已知\ T的情况下求\ grow(T,i)是否是几乎完备的。

解法

我们设左右儿子分别为\ ls,rs。

设\ A_{0}为\ T中\ i节点仅有左儿子的树的集合。

设\ A_{1}为\ T中\ i节点仅有右儿子的树的集合。

设\ B_{0}为\ T中\ i节点有左右儿子，且右儿子是叶子的树的集合。

设\ B_{1}为\ T中\ i节点有左右儿子，且左儿子是叶子的树的集合。

定理 \ grow(T,i)是几乎完备的，要么存在一棵树\ a \in T满足\ i号节点是\ a的叶子，要么\ grow(A_{0},ls),grow(A_{1},rs),grow(B_{0},ls),grow(B_{1},rs)都是几乎完备的。

证明： 第一种情况非常显然，我们只考虑第二种情况。

我们注意到\ grow(T,i)所包含的树有以下三种情况：

前两种情况分别对应\ grow(A_{0},ls),grow(A_{1},rs)，我们考虑最后一种情况。

充分性：如果命题成立，一棵有左右儿子的树不在\ grow(B_{0},ls) \cup grow(B_{1},rs)中当且仅当它的左子树是\ grow(B_{0},ls)中不被包含的部分，右子树是\ grow(B_{1},rs)中不被包含的部分。

必要性：如果\ grow(B_{0},ls)不是几乎完备的，那么右儿子是叶子，左子树不被\ grow(B_{0},ls)包含的树一定不被\ grow(T,i)包含。对于\ grow(B_{1},rs)有一样的证明。

证毕。

由于\ A_{0},A_{1},B_{0},B_{1}是互不相交的，我们直接递归的复杂度不会超过\ O(\sum n)。

由于洛谷没有数据，代码仅在loj上AC。

#include<bits/stdc++.h>
using namespace std;
int ttt,m,n[2002002];
vector<pair<int,int> > ss[2002002];
vector<pair<int,int> > tr[2002002];
int tot=0;
inline bool isleaf(int x,int y)
{
    return (tr[y][x].first==0)&&(tr[y][x].second==0);
}
inline int lson(int x,int y)
{
    return tr[y][x].first;
}
inline int rson(int x,int y)
{
    return tr[y][x].second;
}
inline bool dfs(int u)
{
    if(ss[u].empty()) return 0;
    int i=0;
    while(i<(int)ss[u].size())
    {
        int x=ss[u][i].first,y=ss[u][i].second;
        if(isleaf(x,y)) return 1;
        ++i;
    }
    int lss,rss,llrs,rlrs;
    ++tot;
    lss=tot;
    ++tot;
    rss=tot;
    ++tot;
    llrs=tot;
    ++tot;
    rlrs=tot;
    i=0;
    while(i<(int)ss[u].size())
    {
        int x=ss[u][i].first,y=ss[u][i].second;
        if((lson(x,y))&&(!rson(x,y))) ss[lss].push_back(make_pair(lson(x,y),y));
        else if((!lson(x,y))&&(rson(x,y))) ss[rss].push_back(make_pair(rson(x,y),y));
        else
        {
            if(isleaf(lson(x,y),y)) ss[llrs].push_back(make_pair(rson(x,y),y));
            if(isleaf(rson(x,y),y)) ss[rlrs].push_back(make_pair(lson(x,y),y));
        }
        ++i;
    }
    if((dfs(lss))&&(dfs(rss))&&(dfs(llrs))&&(dfs(rlrs))) return 1;
    return 0;
}
int main()
{
    freopen("surreal.in","r",stdin);
    freopen("surreal.out","w",stdout);
    scanf("%d",&ttt);
    while(ttt--)
    {
        scanf("%d",&m);
        int i=1,j=1;
        while(i<=m)
        {
            tr[i].clear();
            tr[i].push_back(make_pair(0,0));
            scanf("%d",&n[i]);
            j=1;
            while(j<=n[i])
            {
                int l,r;
                scanf("%d%d",&l,&r);
                tr[i].push_back(make_pair(l,r));
                ++j;
            }
            ++i;
        }
        i=1;
        while(i<=tot)
        {
            ss[i].clear();
            ++i;
        }
        tot=0;
        ++tot;
        i=1;
        while(i<=m)
        {
            ss[tot].push_back(make_pair(1,i));
            ++i;
        }
        if(dfs(tot)) printf("Almost Complete\n");
        else printf("No\n");
    }
    return 0;
}