题意 【【NOI2020 超现实树】】对于所有的无标号且区分左右儿子的有根二叉树，定义一棵树T 1 T_1 T1? 可以由另一棵树T 2 T_2 T2? 生长得到，当且仅当可以通过进行若干次将T 2 T_2 T2? 的叶节点替换成某棵二叉树的操作得到。对于一个二叉树集合T \mathscr{T} T，定义g r o w ( T ) \mathrm{grow}(\mathscr{T}) grow(T) 表示所有可以由T \mathscr{T} T 中的树生长得到的树构成的集合。定义g r o w ( T ) \mathrm{grow}(\mathscr{T}) grow(T) 是完备的当且仅当只有有限棵二叉树不在g r o w ( T ) \mathrm{grow}(\mathscr{T}) grow(T) 中。给一个二叉树集合T \mathscr{T} T，问g r o w ( T ) \mathrm{grow}(\mathscr{T}) grow(T) 是否完备。
∑ n , ∑ m ≤ 2 ? 1 0 6 \sum n,\sum m\le 2*10^6 ∑n,∑m≤2?106
分析 定义树枝为那些每个节点的左右子树的s i z e size size 的m i n min min 不超过1 1 1 的二叉树。换句话说，就是那些由一条主链和另外若干个叶子构成的二叉树。
可以发现g r o w ( T ) \mathrm{grow}(\mathscr{T}) grow(T) 是完备的，当且仅当只有有限个树枝不能被生长得到。因为一棵树一定可以由一棵与它深度相同的树枝生长得到，那么若某个深度的树枝均能够被生长得到，所有不小于这个深度的树也就都能被生长得到。
问题转化为是否所有树枝都能被生长得到。对于输入的那些不是树枝的树，生成的也肯定不是树枝，故可以忽略。
除了单独的根节点以外，可以把所有的树枝分成四类：
（1）根有左儿子，但没有右儿子。
（2）根有右儿子，但没有左儿子。
（3）根有左右儿子，且左子树大小为1 1 1。
（4）根有左右儿子，且右子树大小为1 1 1。
注意后两种可能包含重复的树。
每种树枝都有无限种，故g r o w ( T ) \mathrm{grow}(\mathscr{T}) grow(T) 是完备的当且仅当四种树枝都是完备的。考虑如下判断g r o w ( T ) \mathrm{grow}(\mathscr{T}) grow(T) 是否完备的递归算法：
1、若T \mathscr{T} T 中存在一个单独的点，那么g r o w ( T ) \mathrm{grow}(\mathscr{T}) grow(T) 一定是完备的。
2、对于T \mathscr{T} T 中所有能被归到第一类的树枝，设它们左子树构成的集合为T ′ \mathscr{T'} T′，递归判断g r o w ( T ′ ) \mathrm{grow}(\mathscr{T'}) grow(T′) 是否完备。对于后三类树枝也做同样的处理。
3、 g r o w ( T ) \mathrm{grow}(\mathscr{T}) grow(T) 完备当且仅当上一个步骤中每一次递归的集合都是完备的。
时间复杂度O ( ∑ n ) O(\sum n) O(∑n)。
代码
#include
using namespace std;
typedef pair pi;
const int N = 2000005;
int m;
struct Tree
{
int n, *lef, *rig, *size;
void init()
{
scanf("%d", &n);
lef = new int[n + 1];
rig = new int[n + 1];
size = new int[n + 1];
size[0] = 0;
for (int i = 1;
i <= n;
i++) scanf("%d%d", &lef[i], &rig[i]);
}
bool check(int x)
{
if (lef[x] && !check(lef[x])) return 0;
if (rig[x] && !check(rig[x])) return 0;
size[x] = size[lef[x]] + size[rig[x]] + 1;
if (!lef[x] || !rig[x]) return 1;
return min(size[lef[x]], size[rig[x]]) <= 1;
}
void clear()
{
delete[] lef;
delete[] rig;
delete[] size;
}
}t[N];
bool solve(vector & vec)
{
if (!vec.size()) return 0;
for (pi w : vec) if (t[w.first].size[w.second] == 1) return 1;
vector v1, v2, v3, v4;
for (pi w : vec)
{
int x = w.first, y = w.second;
if (!t[x].lef[y]) v1.push_back(make_pair(x, t[x].rig[y]));
if (!t[x].rig[y]) v2.push_back(make_pair(x, t[x].lef[y]));
if (t[x].size[t[x].lef[y]] == 1 && t[x].rig[y]) v3.push_back(make_pair(x, t[x].rig[y]));
if (t[x].size[t[x].rig[y]] == 1 && t[x].lef[y]) v4.push_back(make_pair(x, t[x].lef[y]));
}
vec.clear();
if (!solve(v1) || !solve(v2) || !solve(v3) || !solve(v4)) return 0;
return 1;
}int main()
{
int T;
scanf("%d", &T);
while (T--)
{
scanf("%d", &m);
for (int i = 1;
i <= m;
i++)
{
t[i].init();
if (!t[i].check(1)) t[i].clear(), i--, m--;
}
vector vec;
for (int i = 1;
i <= m;
i++) vec.push_back(make_pair(i, 1));
puts(solve(vec) ? "Almost Complete" : "No");
for (int i = 1;
i <= m;
i++) t[i].clear();
}
return 0;
}
