定义1：两棵树中的$x$和$y$对应当且仅当$x$到根的链与$y$到根的链同构

定义2：$x$和$y$的儿子状态相同当且仅当$x$与儿子所构成的树与$y$与儿子所构成的树同构

根据题中所给的定义，有以下两个的结论（观察可得，证明略）：

结论1：对于两棵树$T_{1}$和$T_{2}$，$T_{1}->T_{2}$当且仅当对于$T_{1}$中的非叶子节点$x$和$T_{2}$中对应的点$y$，$x$和$y$的儿子状态相同

结论2：$grow(\mathscr{T})$几乎完备当且仅当不存在一棵树$T'$使得$\max hT'$

这两个结论都比较显然，考虑继续发掘一些更有用的结论——

定义3：$T$为“链树”当且仅当其存在一条由根到某个叶子的链，使得树上任意一点到链上最近的点距离不超过1

结论3：对于树$T_{1}$和链树$T_{2}$，$T_{1}->T_{2}$当且仅当$T_{1}$为链树且$T_{2}$中所有深度不超过$h(T_{1})$的点所组成的树与$T_{1}$同构

（这个就是结论1通过观察得到的推论，即要求$T_{1}$是$T_{2}$的一个“前缀”（不太严谨），证明略）

结论4：$grow(\mathscr{T})$几乎完备当且仅当不存在一棵“链树”$T'$使得$\max hT'$

证明：观察到仅将树改为了“链树”，由于“链树”的必要条件是树，结论2即必要性

考虑充分性，构造：对于一棵符合条件的树$T'$，将$T'$中最深的点（多个任选一个）到根的链作为$T''$的那条链，保留$T''$中所有到这条链距离为1的点（删去其他点），所构成的树显然为“链树”，接下去证明其符合条件

由于最长的链被保留，因此$\max h<h(T')=h(T'')$

由于$\forall 1\le i\le n,T_{i}\ne >T'$，必然有非叶子节点$x$使得$x$和$T'$中对应的点$y$儿子状态不同，令$a_{i}=y$

1.若$a_{i}$在链上（指“链树”的链），未改变$a_{i}$的儿子状态，仍然符合条件；

2.若$a_{i}$到链上最近的点距离为1，其儿子一定不被保留，则其为叶子节点而$x$为非叶子节点，儿子状态不同；

3.若$a_{i}$不被保留，取$a_{i}$为最近的被保留的祖先$z$，不妨设$a_{i}$在$z$的左子树中，由于$T_{i}$中存在$x$因此$z$在$T_{i}$中对应的点有左子树，而现在$z$的左子树必然为空（否则$z$应该取左儿子），即儿子状态不同

根据这两个结论，可以删去所有不为“链树”的树，然后暴力枚举链树：分为4类，链在(左/右)子树，有无(右/左)儿子，并递归链所在的子树

枚举时，维护一个$vector$表示当前仍然合法（即设枚举到的链树为$T'$，$T_{i}$合法当且仅当$T'->T_{i}$）的“链树”，同时若满足了$T_{i}->T'$（即当前决定儿子状态的点在$T_{i}$中对应的点为叶子）就停止枚举

考虑这一做法的时间复杂度：

当一棵“链树”最深的节点有兄弟，此时不妨视为两棵，这就保证每一棵链树仅被分入4类中的一类

时间复杂度即所有“链树”被划分的次数之和，而每一次划分可以看作“删除”掉当前正在处理的节点，显然这些删除不会重复，因此划分即删除的次数不超过$o(n)$，总复杂度即为$o(n)$

1 #include
2 using namespace std;
3 #define N 2000005
4 vectorv[N];
5 int V,T,t,n,m,r[N],ls[N],rs[N],tot[N];
6 bool pd(int k){
7 if (!tot[k])return 1;
8 if ((!tot[rs[k]])&&(pd(ls[k])))return 1;
9 if ((!tot[ls[k]])&&(pd(rs[k])))return 1;
10 return 0;
11 }
12 bool dfs(){
13 bool v0=0,v1=0,v2=0,v3=0;
14 for(int i=0;i0)+(rs[j+V]>0);
63 }
64 V+=n;
65 if (!pd(r[i])){
66 V-=n;
67 i--;
68 m--;
69 }
70 }
71 T=0;
72 v[0].clear();
73 for(int i=1;i<=m;i++)v[0].push_back(r[i]);
74 if (dfs())printf("No\n");
75 else printf("Almost Complete\n");
76 }
77 return 0;
78 }