有意思的问题。设原树为 \(G\)。
手玩一下，不难发现，若子树 \(T\) 与 \(G\) 中任何一颗子树都不同构，那么对于任意树 \(S\)，其中 \(T\) 是 \(S\) 的子树，\(S\) 同样不与 \(G\) 中任何一颗子树同构。
进一步地，假设我们已经知道了一颗最小的 \(T\)，我们使得剩下的 \(|G|-|T|\) 棵子树全部包含 \(T\)，则可以使得最大不构子树数为 \(|G|-|T|+1\)。这对应的构造方案就是构造长为 \(|G|-|T|\) 的链，并将 \(T\) 接在下面。
这显然是最优解，对这个解进行任何的改动都会导致答案变差。
那么进一步研究，可以得出 \(|T_{\min}|\) 必然是一个极小的数字。为什么？设 \(x=|T_{\min}|\)，则设 \(a_{i}\) 为 \(i\) 个点构成的不同构树个数，设 \(b_i\) 为 \(i\) 个点构成的不同构二叉树的个数，则显然有 \(a_{i}\ge b_{i}\)，而我们知道后者是卡特兰数，一个增长为指数级的数列。
则必然有 \(x< a_{m}\)，其中 \(a_{m}\ge |G|\) 且 \(m\) 为满足条件的最小正整数。
这里可以推出 \(x\) 的范围非常小。考虑枚举 \(x\)，判断是否可行。只要构造出了一个符合的 \(T\)，即可立即输出。
那么怎么判断呢？很简单，我们将 \(x\) 可以构成的每一棵树全部枚举，然后依次判断是否同构即可。这个时间复杂度？
可以先预处理出 \(G\) 中的不同构子树以便判断。
时间复杂度怎么说，设单次判断时间复杂度为 \(t\)，则总时间复杂度为 \(O(nt)\)。因为在暴力时最多枚举 \(n\) 个树。
进一步地，具体实现怎么办？显然我们需要对一棵同构树进行哈希。
哈希方法不同，比较常见的有基于素数的哈希，这里介绍一种常数较大但绝无冲突的办法。（毕竟会有人对着代码卡哈希函数）
我们可以使用一个集合作为哈希函数。显然一个树必然是由更小的树组合而来。我们可以考虑对原树中每一棵不同构树标号，并且它所对应的集合为它的儿子的编号集合（注意是可重有序集）。
如下：
#define ve vector<int>
map<ve ,int>h;
int id[N],n,t,cnt,num;
int get(ve &a){
if(h.find(a)!=h.end())return h[a];
int id=h.size();h[a]=id;
return id;
}
void dfs(int u,int fa){
ve a;a.clear();
for(auto v:g[u]){
if(v==fa)continue;
dfs(v,u);
a.push_back(id[v]);
}
sort(a.begin(),a.end());
id[u]=get(a);cnt=max(cnt,id[u]);
return ;
}
这样做常数是极大的，但总体时间复杂度没有影响。
然后我们考虑进行枚举拼凑这一步。先枚举 \(x\) 的大小，然后我们用一个暴力的深度优先搜索找 \(T\) 的子树，进行拼凑 \(x\)。只要最终组合的 \(T\) 不存在同构树，那就找到了解，输出即可。
方案怎么输出？我们本身就记录了每一棵树的构成儿子，可以直接遍历这棵树，并且记录当前父亲编号进行输出。
注意最后如果搜不到，此时 \(n\) 必然极小，直接输出原树即可。