比较智慧,但如果能想到链树的话其实不难。(为啥全机房都在刷 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;
}
最后只需要穿上去就好了。
原文地址:http://www.cnblogs.com/pref-ctrl27/p/16846424.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性