链接
为什么我没有看到第5,6个样例？
题目大意
定义一颗二叉树 (S) 将若干个叶子节点替换为任意二叉树后的树与 (T) 同构，称为 (S) 包含 (T)。
现在给定 (n) 颗树 (S_i)，问对于所有二叉树，是否只有有限个二叉树没有任意一个 (S_i) 包含。
题解
结论题。
首先我们可以把题目看成：问能否构造一颗高度无限的二叉树，使其不被任意一个 (S_i) 包含。
考虑包含的性质，我们可以再次转换问题，即：问能否构造一颗无限长的二叉树，使对于任意 (S_i) ，存在一个非叶子节点的儿子信息不同（有/无左儿子，有/无右儿子）。
再考虑一个很显然的性质：如果有两棵二叉树 (S,T)，(T) 根的左子树不被 (S) 根的左子树包含，那么 (T) 一定不被 (S) 包含。
首先，如果存在 (S_i) 是一个节点，那么一定不存在。
否则贪心地从根考虑构造：可以发现，如果根的左子树中存在一种树，不被任何 (S_i) 根的左子树包含，那么就存在一颗无限长的二叉树，使其不被任意一个 (S_i) 包含。
即我们希望在左子树中构造一种树，使其不被当前集合中任何 (S_i) 包含。如果成功，由于上述性质，意味着右子树无论怎么构造都不会被包含。
很明显，假如这种树存在，其中一定包含只有根结点的树。所以构造只有根结点的树（即叶子）一定不会劣。
反之，如果左子树中不存在这样的一种树，即当前的 (S_i) 中存在一棵树，其根的左儿子是叶子。那么这样作为构造方就有了一种选择：选/不选左儿子。可以发现第一条对应的集合变成了“根有左儿子且左儿子是叶子”，第二条对应的集合变成了“根没有左儿子”。
对右儿子同理。可以发现，作为构造方，我们现在有4种选择：
- 空出左子树，递归构造右子树。
- 空出右子树，递归构造左子树。
- 左子树放叶子，递归构造右子树。
- 右子树放叶子，递归构造右子树。
可以发现，这样把集合 (S_i) 分成了4份。对于每份集合，必然存在无限种构造使该树不被其他集合的树包含。
对于4种情况，递归处理即可。
特别的，对于左右子树都是叶子的树 (S)，意味着构造3,4都会被 (S) 包含，所以这种情况下只需要递归构造1,2即可。
理论上好像可以被卡到 (O(nsqrt n))，但实际跑得飞快。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define N 3000010
using namespace std;
vector<int> ls[N],rs[N];
struct node{
int t,u;
};
vector<node>id;
inline bool lev(node a){return !ls[a.t][a.u] && !rs[a.t][a.u];}
inline bool have_ls(node a){return ls[a.t][a.u];}
inline bool have_rs(node a){return rs[a.t][a.u];}
inline node lson(node a){return (node){a.t,ls[a.t][a.u]};}
inline node rson(node a){return (node){a.t,rs[a.t][a.u]};}
bool solve(vector<node> &s)
{
if(s.empty()) return false;
for(node i:s) if(lev(i)) return true;
vector<node>s1,s2,s3,s4;
bool can=false;
for(node i:s)
if(!have_ls(i)) s1.push_back(rson(i));
else if(!have_rs(i)) s2.push_back(lson(i));
else if(lev(lson(i)) && lev(rson(i))) can=true;
else if(lev(lson(i))) s3.push_back(rson(i));
else if(lev(rson(i))) s4.push_back(lson(i));
s.clear();
if(s1.empty() || s2.empty() || (!can && (s3.empty() || s4.empty()))) return false;
return solve(s1) && solve(s2) && (can || (solve(s3) && solve(s4)));
}
int main()
{
freopen("surreal.in","r",stdin);
freopen("surreal.out","w",stdout);
int t;
scanf("%d",&t);
while(t --> 0)
{
int n;
scanf("%d",&n);
id.resize(n);
for(int i=0;i<n;i++)
{
int tn;
scanf("%d",&tn);
id[i]=(node){i,1};
ls[i].resize(tn+1),rs[i].resize(tn+1);
for(int j=1;j<=tn;j++) scanf("%d%d",&ls[i][j],&rs[i][j]);
}
puts(solve(id)?"Almost Complete":"No");
}
return 0;
}