最长的树结构序列

KeyTo9_Fans

假设树的每个节点都可以染成n种颜色中的其中一种，要求构造一个尽可能长的、满足以下要求的“树序列”：

1.第1棵树只有1个根节点，第2棵树最多2个节点，第3棵树最多3个节点，……，第i棵树最多i个节点

2.后面的树删去任意多个节点，然后把剩余节点按删点前的【祖先-后代】关系连起来后，得到的这棵树不能和前面的任何一棵树完全相同

问：满足上述要求的树序列，最长可以有多长？

我目前求出了n=1和n=2的结果，如下：

当n=1时，最长1棵树，第2棵树无论怎么构造，删剩1个点后都和第1棵树完全相同，因此只能构造1棵树。

当n=2时，我最多可以构造3棵树，假设有红色和蓝色，构造方案如下：

第1棵树是1个红色根节点，

第2棵树是蓝色根节点下面连一个蓝色叶子节点，删去任意节点都和第1棵树颜色不同

第3棵树只有1个蓝色根节点，和前面2棵树都不完全相同

至此两种颜色都用完了，无法再构造下一棵树了

当n=3时，最多可以构造多少棵树呢？如何构造？

KeyTo9_Fans

我用3种颜色（用数字1、2、3表示）构造了10棵树，如下图所示：



目前的构造情况如下：

第1棵树用掉了颜色1，以后的树节点全都不能用颜色1，只能用颜色2或3

第2棵树用掉了颜色2后面的2，以后所有的2后面都只能是3，不能是2

第3棵树用掉了颜色2后面并排的2个3，以后所有的2后面都不能出现2个分支有3，最多只能有1个分支有3

第4棵树用掉了颜色2后面连续3个3，以后所有的2后面都只剩下3种接法了：第1种接法是啥都不接；第2种接法是只接1个3；第3种接法是接1个3后面再接1个3；没有第4种接法了

再这样2下去，2很快就绝后了，为了保留2后面接2个3的权利，第5棵树用3做树根，其中一条分支接233

但构造到第7棵树，3233这条分支也耗尽了，旁边不能接2，不能接2个有直系血亲的3，也不能接3个无直系血亲的3，最多只能接2个无直系血亲的3了

为了保留3233旁边接2个3的权利，我从第8棵树开始使用“323”结构，但到了第10棵树，把3个323结构的权利用光了，后面最多只能用2个并列的323结构了

感觉剩下的结构不多了，不知道还能构造多少棵树，也不知道有没有更“长寿”的构造方案