分析
我们把每个节点都满足有一棵大小 $\leq 1$ 的子树的树称作「树枝」。
那么，$\mathrm{grow}(\mathscr{T})$ 是几乎完备的当且仅当所有高度为 $h$ 的树枝都在 $\mathrm{grow}(\mathscr{T})$ 中，这里的 $h$ 为 $\mathscr{T}$ 中树高的最大值。证明比较简单，因为任意一棵高度 $>h$ 的树都能由某个高度为 $h$ 的树枝生成，而一个高度为 $h$ 的树枝可以生成的无穷多棵树均不能被其它高度为 $h$ 的树枝生成。
这个定理实际上等价于 $\mathrm{grow}(\mathscr{T})$ 是几乎完备的当且仅当仅有有限个树枝不在 $\mathrm{grow}(\mathscr{T})$ 中。
考虑到树枝只能由树枝生成，所以我们可以去掉 $\mathscr{T}$ 中所有不是树枝的树。
设 $\mathrm{solve}(\mathscr{T})$ 表示 $\mathrm{grow}(\mathscr{T})$ 是否几乎完备。显然 $\mathscr{T}$ 中有一个单独节点时 $\mathrm{solve}{\mathscr{T}}=1$，否则我们把 $\mathscr{T}$ 中所有树分成四类：
- 没有左儿子的，将其右子树集合记做 $\mathscr{A}$。
- 没有右儿子的，将其左子树集合记做 $\mathscr{B}$。
- 左子树大小为 $1$ 的，将其右子树集合记做 $\mathscr{C}$。
- 右子树大小为 $1$ 的，将其左子树集合记做 $\mathscr{D}$。
那么如果 $\mathrm{solve}(\mathscr{A})$、$\mathrm{solve}(\mathscr{B})$、$\mathrm{solve}(\mathscr{C})$、$\mathrm{solve}(\mathscr{D})$ 都为真，则 $\mathrm{solve}{(\mathscr{T})}$ 为真。因为可能的树枝只能由这四种方式生成，如果有一种不几乎完备则可以构造出无数棵不在 $\mathrm{grow}(\mathscr{T})$ 中的树。
时间复杂度大概是 $\mathcal{O}(\sum n)$ 的。
代码
// ====================================
// author: M_sea
// website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;
int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=2000000+10;
int m,tot=0,ls[N],rs[N];
vector<int> t;
bool isleaf(int o) { return !ls[o]&&!rs[o]; }
bool solve(vector<int> t) {
if (t.empty()) return 0;
for (int o:t) if (isleaf(o)) return 1;
vector<int> t1,t2,t3,t4;
for (int o:t) {
if (!ls[o]) t1.emplace_back(rs[o]);
if (!rs[o]) t2.emplace_back(ls[o]);
if (ls[o]&&rs[o]) {
if (isleaf(ls[o])) t3.emplace_back(rs[o]);
if (isleaf(rs[o])) t4.emplace_back(ls[o]);
}
}
return solve(t1)&&solve(t2)&&solve(t3)&&solve(t4);
}
int main() {
int T=read();
while (T--) {
t.clear(),tot=0;
m=read();
for (int i=1;i<=m;++i) {
int n=read(); t.emplace_back(tot+1);
for (int j=1;j<=n;++j) {
ls[tot+j]=read(); if (ls[tot+j]) ls[tot+j]+=tot;
rs[tot+j]=read(); if (rs[tot+j]) rs[tot+j]+=tot;
}
tot+=n;
}
puts(solve(t)?"Almost Complete":"No");
}
return 0;
}