(mathcal{Description})
Link.
对于非空二叉树 (T)，定义 (operatorname{grow}(T)) 为所有能通过若干次“替换 (T) 的某个叶子为任意非空二叉树”的操作得到的二叉树集合；对于非空二叉树集合 (mathscr T)，定义 (operatorname{grow}(mathscr T)=igcup_{Tin{mathscr T}}operatorname{grow}(T))。多次询问，每次给定一个 (mathscr T)，询问是否仅有有限个二叉树不在 (operatorname{grow}(mathscr T)) 中。二叉树判等时区分左右儿子，点无编号。
设单棵树的结点数为 (n)，则 (sum nle2 imes10^6)。
这 tm 才叫简要题意。
(mathcal{Solution})
谨以本题解表达去年做题的兔子对题面的赞美。
(mathbf{X1})：我们先来研究一个几乎完备的 (operatorname{grow}(mathscr T)) 吧，在这样的 (mathscr T) 中，会不会有些树不可起到使 (operatorname{grow}(mathscr T)) 完备的作用呢？
(mathbf{X2})：嗯，每片叶子都可以生长出任何二叉树，那么，起到决定性作用的是否叶子们的深度？
(mathbf{X1})：那就先控制深度信息！我发现书上也有在这个思路下衍生的定义。
定义：二叉树集合 (mathscr B_n) 为高度为 (n) 的全体二叉树集的基，定义为：
[mathscr B_n={T~|~h(T)=nland(~ otexist T',~h(T')=nland Tinoperatorname{grow}(T'))} ]
(mathbf{X2})：简而言之，这个 (mathscr B_n) 包含了所有高度为 (n) 且不能被其他高度为 (n) 的树“生长”出来。很显然，(operatorname{grow}(mathscr B_n)) 包含了所有高度为 (n) 的二叉树！
(mathbf{X1})：继续深入的话……说不定 (mathscr B_n) 里的 (T) 也有特殊性质呢。
(mathbf{X2})：（手玩片刻）呀！这样的 (T) 看上去都很“瘦小”，具体地，如果结点 (u) 同时拥有左右儿子，那么必然有至少一个儿子是叶子。嗯！这是能够证明的结论。
证明：记 (p(T)) 为真时，(T) 满足上述性质，否则则不满足。设 (h(T)=n)，我们希望证明
[p(T)Leftrightarrow Tinmathscr B_n ]对于 (p(T)Rightarrow Tinmathscr B_n)，取出 (T) 中一定存在的自根而下长为 (n) 的树链 (L)，这样的链是单独的一条或者在末尾分叉的两条。我们可以断言，若有 (h(T')=n,Tinoperatorname{grow}(T'))，则 (T') 必然满足 (Lsube T')。而对于其余叶子，由于它们的父亲都在 (T') 的点集中且不是叶子，所以它们也必然在 (T') 的点集中。最终，发现 (T=T')，故命题成立。
另一边，(p(T)Leftarrow Tinmathscr B_n)，仍使用反证法。对于不满足条件的 (T)，取出一个左右儿子存在且均不是叶子的结点 (u)，它必然有一个儿子 (v) 满足删去 (v) 子树后 (h(T)=n)。则可将 (v) 子树“逆向生长”为单点 (v)，此时得到的 (T') 满足 (h(T)=n) 且 (Tinoperatorname{grow}(T'))，所以 (T otinmathscr B_n)，假设矛盾，原命题成立。
综上，命题得证。
(mathbf{X1})：离成功更近一步！把这个强大的结论用于题目本身，是不是说，如果 (Tinmathscr T) 不满足上述条件，就能从 (mathscr T) 中剔除 (T) 而不改变 (operatorname{grow}(mathscr T)) 的完备性？……没错！如果 (T) 是这样一棵树，且不存在 (T'inmathscr Tsetminus{T}) 使得 (Tinoperatorname{grow}(T'))，如果存在某棵树只能由 (T) 生长出来，我们一定能找到这棵树中一个左右儿子均存在且不是叶子的结点 (u)，将它的一个儿子替换为单点。那么，这棵树的 (operatorname{grow}) 集合与 (operatorname{grow}(mathscr T)) 交集为空！
(mathbf{X2})：接下来就只需要直面问题，尝试判断 (operatorname{grow}(mathscr T)) 是否几乎完备。我们从一棵“希望与 (operatorname{grow}(mathscr T)) 匹配的树”的视角出发，设当前结点为 (u)，如果 (u) 子树能够匹配上：
- 需要 (Tinmathscr T)，(T) 在此位置上的结点是叶子，这强于以下所有条件。
- (u) 只有左儿子，需要一个只有左儿子的 (T)；
- (u) 只有右儿子，需要一个只有右儿子的 (T)；
- (u) 左儿子是叶子，需要同样情况的 (T)；
- (u) 右儿子是叶子，需要同样情况的 (T)；
- (u) 左右儿子都是叶子，3. 4. 任意。
我们定义 (operatorname{syno}(mathscr T)) 是一棵四叉树，它是对 (mathscr T) 的等价概括。我们可以每个 (T) 合并入其中，依照 1. 2. 3. 4. 四种情况划分儿子编号。最后，定义 (f(operatorname{syno}(mathscr T),u)) 该四叉树中 (u) 子树的完备性，有
最终，(f(operatorname{syno}(mathscr T),operatorname{root})) 即为答案。复杂度 (mathcal O(sum|T|))！
(mathbf{X1})：不过我发现一个问题欸，为什么题目描述比题解还长呢？
(mathcal{Code})
/* Clearink */
#include <cstdio>
#include <cassert>
#define rep( i, l, r ) for ( int i = l, rep##i = r; i <= rep##i; ++i )
#define per( i, r, l ) for ( int i = r, per##i = l; i >= per##i; --i )
inline char fgc() {
static char buf[1 << 17], *p = buf, *q = buf;
return p == q && ( q = buf + fread( p = buf, 1, 1 << 17, stdin ), p == q )
? EOF : *p++;
}
inline int rint() {
int x = 0; char s = fgc();
for ( ; s < '0' || '9' < s; s = fgc() );
for ( ; '0' <= s && s <= '9'; s = fgc() ) x = x * 10 + ( s ^ '0' );
return x;
}
const int MAXN = 2e6;
int m;
struct BinaryTree {
int node, ch[MAXN + 5][2];
inline void clear() {
rep ( i, 1, node ) ch[i][0] = ch[i][1] = 0;
node = 0;
}
inline void read() {
clear(), node = rint();
rep ( i, 1, node ) ch[i][0] = rint(), ch[i][1] = rint();
}
inline int type( const int u ) const {
/*
-1: illegal node (not a basic tree).
0: left only.
1: right only.
2: left chain and right leaf.
3: right chain and left leaf.
4: 2&3.
*/
int lc = ch[u][0], rc = ch[u][1];
assert( lc || rc );
if ( !rc ) return 0;
if ( !lc ) return 1;
bool lf = !ch[lc][0] && !ch[lc][1], rf = !ch[rc][0] && !ch[rc][1];
if ( lf && rf ) return 4;
if ( rf ) return 2;
if ( lf ) return 3;
return -1;
}
inline bool check( const int u ) {
if ( !u || ( !ch[u][0] && !ch[u][1] ) ) return true;
return ~type( u ) && check( ch[u][0] ) && check( ch[u][1] );
}
} binT;
struct SynopsisTree {
int node, ch[MAXN + 5][4];
bool tag[MAXN + 5];
inline void clear() {
rep ( i, 1, node ) {
ch[i][0] = ch[i][1] = ch[i][2] = ch[i][3] = 0,
tag[i] = false;
}
node = 1;
}
inline void storage( const BinaryTree& T, int& u, const int v ) {
if ( !v ) return ;
if ( !u ) u = ++node;
if ( tag[u] ) return ;
if ( !T.ch[v][0] && !T.ch[v][1] ) return void( tag[u] = true );
int f = T.type( v );
if ( !f ) storage( T, ch[u][0], T.ch[v][0] );
else if ( f == 1 ) storage( T, ch[u][1], T.ch[v][1] );
else {
if ( f == 2 || f == 4 ) storage( T, ch[u][2], T.ch[v][0] );
if ( f == 3 || f == 4 ) storage( T, ch[u][3], T.ch[v][1] );
}
}
inline bool complete( const int u ) {
if ( !u || tag[u] ) return !!u;
return complete( ch[u][0] ) && complete( ch[u][1] )
&& complete( ch[u][2] ) && complete( ch[u][3] );
}
} synT;
int main() {
for ( int T = rint(), root = 1; T--; ) {
synT.clear(), m = rint();
rep ( i, 1, m ) {
binT.read();
if ( binT.check( 1 ) ) synT.storage( binT, root, 1 );
}
puts( synT.complete( 1 ) ? "Almost Complete" : "No" );
}
return 0;
}