• P6776-[NOI2020]超现实树


    正题

    题目链接:https://www.luogu.com.cn/problem/P6776


    题目大意

    定义一次操作为将一棵树的叶子换成另一棵树。
    定义一棵树 T T T g r o w ( T ) grow(T) grow(T)表示所有树 T T T能够通过操作变成的树的集合。

    现在给出 m m m棵树 T i T_i Ti,定义 S S S为所有 g r o w ( T i ) grow(T_i) grow(Ti)的交集。

    S S S是否几乎完备(指仅有有限棵树不在集合 S S S内)。

    1 ≤ ∑ n , ∑ m ≤ 2 × 1 0 6 , T ≤ 100 1\leq \sum n,\sum m\leq 2\times 10^6,T\leq 100 1n,m2×106,T100


    解题思路

    我们考虑所有的树(因为我们要细分到子树考虑所以这里考虑上空树)中,一个点可以到达所有非空树,其他非空树都不能到达一个点,而空树和一个点不能相互到达。

    我们先把所有读入的树并起来,然后每到一个点就分别考虑左右两边是否完备。

    如果所有的树都存在一个点 x x x使得左右两边都至少有两个点,那么这棵树就没有作用了,因为某一边一个点或者空树它们都到达不了,那另一边就可以随便排了。

    所以对于每个位置我们要保证左/右边为 0 0 0个点和左/右边为 1 1 1为一个点的树中,在另一边都要是几乎完备的就合法了。

    时间复杂度: O ( ∑ n ) O(\sum n) O(n)


    code

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<vector>
    #include<cctype>
    #define mp(x,y) make_pair(x,y)
    #define ull unsigned long long
    using namespace std;
    const int N=2e6+10;
    const ull g=131;
    struct node{
    	int id,x;
    	node(int iid,int xx)
    	{id=iid;x=xx;return;}
    };
    const int o[2]={0,0};
    int Case,n,m,cnt,t[N][2],siz[N];
    ull pw[N];vector<node>q[N];
    int read(){
    	int x=0,f=1;char c=getchar();
    	while(!isdigit(c)){if(c=='-')f=-f;c=getchar();}
    	while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    	return x*f;
    }
    struct Tree{
    	vector<int> ch[2];
    	vector<int> siz;
    	void build(int &x,int p){
    		if(!x)x=++cnt;
    		if(ch[0][p])build(t[x][0],ch[0][p]);
    		if(ch[1][p])build(t[x][1],ch[1][p]);
    		siz[p]=1+siz[ch[0][p]]+siz[ch[1][p]];
    		return;
    	}
    	void init(int p){
    		n=read();siz.resize(n+1);
    		ch[0].resize(n+1);
    		ch[1].resize(n+1);
    		for(int i=1;i<=n;i++)
    			ch[0][i]=read(),ch[1][i]=read();
    		int rt=1;build(rt,1);
    		q[1].push_back(node(p,1));
    	}
    	void Clear()
    	{ch[0].clear();ch[1].clear();siz.clear();}
    	bool isSon(int x){return (!ch[0][x]&&!ch[1][x]);}
    }T[N];
    bool solve(int x){
    	for(int i=0;i<q[x].size();i++)
    		if(T[q[x][i].id].isSon(q[x][i].x))return 1;
    	if(!q[x].size()||!t[x][0]||!t[x][1])return 0;
    	bool ans=1;
    	for(int i=0;i<q[x].size();i++){
    		int id=q[x][i].id,y=q[x][i].x;
    		if(T[id].siz[T[id].ch[1][y]]==0&&T[id].ch[0][y])
    			q[t[x][0]].push_back(node(id,T[id].ch[0][y]));
    	}
    	ans&=solve(t[x][0]);
    	q[t[x][0]].clear();
    	for(int i=0;i<q[x].size();i++){
    		int id=q[x][i].id,y=q[x][i].x;
    		if(T[id].siz[T[id].ch[1][y]]==1&&T[id].ch[0][y])
    			q[t[x][0]].push_back(node(id,T[id].ch[0][y]));
    	}
    	ans&=solve(t[x][0]);
    	q[t[x][0]].clear();
    	
    	for(int i=0;i<q[x].size();i++){
    		int id=q[x][i].id,y=q[x][i].x;
    		if(T[id].siz[T[id].ch[0][y]]==0&&T[id].ch[1][y])
    			q[t[x][1]].push_back(node(id,T[id].ch[1][y]));
    	}
    	ans&=solve(t[x][1]);
    	q[t[x][1]].clear();
    	for(int i=0;i<q[x].size();i++){
    		int id=q[x][i].id,y=q[x][i].x;
    		if(T[id].siz[T[id].ch[0][y]]==1&&T[id].ch[1][y])
    			q[t[x][1]].push_back(node(id,T[id].ch[1][y]));
    	}
    	ans&=solve(t[x][1]);
    	q[t[x][1]].clear();
    	return ans;
    }
    int main()
    {
    //	freopen("surreal4.in","r",stdin);
    	scanf("%d",&Case);pw[0]=1;
    	for(int i=1;i<N;i++)pw[i]=pw[i-1]*g;
    	while(Case--){
    		for(int i=1;i<=cnt;i++)q[i].clear(),t[i][0]=t[i][1]=0;
    		for(int i=1;i<=m;i++)T[i].Clear();
    		cnt=1;m=read();
    		for(int p=1;p<=m;p++)
    			T[p].init(p);
    		if(solve(1))puts("Almost Complete");
    		else puts("No");
    	}
    	return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
  • 相关阅读:
    多线程与并发 - 常见的几种锁的实现方式
    redis中集合的相关命令
    Java 内存模型
    Notepad++使用技巧
    智慧农业新篇章:拓世法宝AI智能直播一体机助力乡村振兴与农业可持续发展
    ToBeWritten之车联网安全中常见的TOP 10漏洞
    微信扫码跳转到小程序内部,浏览器扫码跳转到App 内部,如果手机上没有安装App ,跳转到下载页
    10 大最佳网络分析工具介绍
    大数据Hadoop之——总结篇
    vue前端解决跨域【vue.config.js】
  • 原文地址:https://blog.csdn.net/Mr_wuyongcong/article/details/125504645