[ZJOI2018]树

鸽子更博了！

如今大学已尘埃落定，终于成功进入清华，不过不在计算机系。还是希望将$OI$作为一种爱好，也想找机会参加$acm$，因此还是会时不时复健一下。这一题是我记忆中攻克最艰难、解题后也最痛快的一题，因此印象深刻。当然我早已忘了具体的步骤，因此最近重做了一遍，也算是对自己的魔鬼训练吧。

与群论相关的前置知识： 设$G$是所有长度为$n$的置换构成的群，$X$是一些长度为$n$的序列构成的集合。如果将$G$作用于$X$，那么： 对于$x\in X$，称$\{y\in X|y=f(x),f\in G\}$为$x$的轨道，记为$Orbit(x)$，对于$y\in Orbit(x)$，称$y$为$x$的等价类。 对于$x\in X$，称$\{f\in G|x=f(x)\}$为$x$的稳定化子，记为$SG(x)$。 对于$f\in G$，称$\{x\in X|x=f(x)\}$为$f$的不动点，记为$fix(f)$。

与题意类似，我们定义两个森林同构，当且仅当可以通过某种一一对应关系，使得一个森林的任意一棵树都和另一森林对应的树同构。

设$cn{t}_n$为$n$个点的无标号有根树个数，并令所有树从$1$到$cn{t}_n$标号。

那么令$S_{n,i}$表示所有按照题目要求构造的带标号有根树中，与$n$个点的$i$号无标号有根树同构的那一部分构成的集合。

由于按照题意建立的$n$个点的树共有$(n-1)!$种，因此

$$ans=\frac{1}{(n-1){!}^k}\sum _{i=1}^{cn{t}_n}|S_{n,i}{|}^k$$

那么重点关注后半部分，尝试利用动态规划的方法解题。那么令：

$$d{p}_n=\sum _{i=1}^{cn{t}_n}|S_{n,i}{|}^k$$

考虑如何转移。回想判断无标号有根树同构的过程：先将根的所有子树按照一定规则排序，逐一比较即可。那么是否可以先枚举排序后在最后的子树，将其删去递归求解，再考虑这棵子树的贡献呢？

但是，如果枚举排在最后的子树，那么就隐含了条件：对于递归的树，其根的所有子树的优先级一定在该子树之前（或者就是该子树），而子树的数目众多，无法比较好的设计状态。

但这样的思考并不是毫无意义的。虽然枚举最后的子树不太现实，但也许可以退而求其次，对子树先进行一个“粗略的划分”，而非直接一个个分离。不难想到先根据子树大小从小到大初步排序，每次删去大小最大的那一批子树，对剩余的树进行递归求解，再考虑这些相同大小的子树的贡献。那么对递归求解的树的额外要求，就转变为了根的子树大小不能超过某个值，不仅状态大量减少，考虑起来也非常方便。

那么为了方便，我们记$mxs(S_{n,i})$表示对于集合$S_{n,i}$中的树，他们根的子树的最大大小，类似记$mns(S_{n,i})$表示最小的。根据上面的想法，可以设计辅助状态：

$$tm{p}_{n,p}=\sum _{i=1}^{cn{t}_n}[mxs(S_{n,i})\le p]|S_{n,i}{|}^k$$

则有$d{p}_n=tm{p}_{n,n-1}$。再考虑状态的转移。那么就枚举大小为$p$的根的子树的数目，分配标号，再将前后部分独立考虑。前半部分可以递归到之前的状态，但后半部分无法递归，需要单独解决，表示成式子，就是：

$$tm{p}_{n,p}=\sum _{u=0}^{\lfloor \frac{n-1}{p}\rfloor }{(\genfrac{}{}{0ex}{}{n-1}{u\ast p})}^{k}tm{p}_{n-u\ast p,p-1}\ast f_{p,u}$$

因为$1$号点显然是根，所以实际分配的标号只有$n-1$个。其中：

$$f_{p,u}=\sum _{i=1}^{cn{t}_{u\ast p+1}}[mns(S_{u\ast p+1,i})=mxs(S_{u\ast p+1,i})=p]|S_{u\ast p+1,i}{|}^k$$

表示需要单独解决的那一部分。之所以大小为$u\ast p+1$，是因为我们给着$u$棵大小为$p$的树额外加了一个形式上的根，方便考虑问题。那么第一步先考虑标号的分配。

按照常规来讲，标号的分配应该是$(\genfrac{}{}{0ex}{}{u\ast p}{p,p,\dots ,p})$种情况，但在此处，由于根的所有子树之间是没有顺序的（这也是之前进行“粗略的划分”遗留下来的问题），因此如果出现两棵相同的子树，它们的地位完全等价，也即即使赋予它们的标号互换，得到的也是同一种结果。但是$(\genfrac{}{}{0ex}{}{u\ast p}{p,p,\dots ,p})$的分配方式显然将互换前后看作不一样的。

看来$(\genfrac{}{}{0ex}{}{u\ast p}{p,p,\dots ,p})$并不能适用于所有情况，还需要进行进一步的分类讨论。那么我们假设其中某一个$S_{u\ast p+1,i}$，其根的子树可以分为$m$类本质不同的，且数目分别为$a_1,a_2,a_3,\dots ,a_m((\sum _{t=1}^m{a}_t)=u)$，也不妨将$a$不降序排序。对于同一类的子树内部，任意两棵树都可以互换标号，因此分配给这一类的$a_t$组标号彼此是无序的，需要将分配标号方案数乘以$\frac{1}{a_t!}$。因此对这一情况，分配的方法数应该为：

$$(\genfrac{}{}{0ex}{}{u\ast p}{p,p,\dots ,p})\ast (\prod _{t=1}^m\frac{1}{a_t!})=\frac{(u\ast p)!}{(p!{)}^u}\ast (\prod _{t=1}^m\frac{1}{a_t!})$$

初步解决分配标号的问题后，我们再考虑下一步操作。此时只要将$u$棵子树内部的标号都看作是$1,2,\dots ,p$即可，此时可以去掉形式上的根，将其转化为$u$棵树的森林。根据之前的定义，我们可以将全体大小为$p$的无标号有根树编号为$1,2,\dots ,cn{t}_p$。对于某一个森林，将其每一棵树对应到这棵树所属类别的编号，我们可以将该森林与一个无序可重集合$\tilde{x}$对应。将所有$\tilde{x}$组成的集合记作$\tilde{X}$。

则$\tilde{x}$满足两个性质：恰好包含$u$个数，且每个数都在$1$到$cn{t}_p$之间。也可以将$a_t$的概念从$S_{u\ast p+1,i}$迁移到$\tilde{x}$上。不妨记${\omega }_{\tilde{x}}$为属于$\tilde{x}$对应森林的带标号森林的数目的$k$次幂，那么$f_{p,u}$可以表示为：

$$f_{p,u}=\sum _{\tilde{x}\in \tilde{X}}\frac{(u\ast p){!}^k}{(p!{)}^{u\ast k}}\ast (\prod _{t=1}^m\frac{1}{a_t{!}^k})\ast {\omega }_{\tilde{x}}$$$$\begin{array}{}\text{(}\ast \text{)}& =\frac{(u\ast p){!}^k}{(p!{)}^{u\ast k}}\ast (\sum _{\tilde{x}\in \tilde{X}}(\prod _{t=1}^m\frac{1}{a_t{!}^k})\ast {\omega }_{\tilde{x}})\end{array}$$

因为在分配完标号以后，树的同构就转化为了森林的同构。

然而，由于$\tilde{x}$是无序可重集合，这非常不利于枚举，因此直接进行计算也非常麻烦。希望能将其转化为有序可重集合（即一个长度为$u$的序列）再进一步解决问题。

那么设$x$是一个长度为$u$的序列，且每一个数都在$1$到$cn{t}_p$之间。将所有这样的$x$的集合记做$X$。如果$x$无序化后能和某一个$\tilde{x}$相同，我们称$x$对应到$\tilde{x}$。

由于$\tilde{x}$是一个可重的集合，因此对应到$\tilde{x}$的$x$的数目是变化的，不能直接枚举$x$。想要利用$X$得到一个和$(\ast )$相类似的等式，还需要借助置换群。

为了表达方便，用前置知识中的术语来表达。设$G$是所有长度为$u$的置换构成的群，将$G$作用于$X$。

那么对于一个$Orbit(x)$，所有在这一集合内的$y$都对应到相同的$\tilde{x}$，可以用$Orbit(x)$来代替$\tilde{x}$。将$a_t$、$\omega$的概念迁移到$x$上，我们可以得到与$(\ast )$类似的式子：

$$f_{p,u}=\frac{(u\ast p){!}^k}{(p!{)}^{u\ast k}}\ast (\sum _{x\in X}(\prod _{t=1}^m\frac{1}{a_t{!}^k})\ast \frac{{\omega }_x}{|Orbit(x)|})$$

不难发现$|Orbit(x)|=\frac{u!}{\prod _{t=1}^m{a}_t!}$。此时有一个难点，就是${\omega }_x$的计算。先尝试将所有$a$相同的$x$发在一起计算（此时$(\prod _{t=1}^m\frac{1}{a_t{!}^k})$和$|Orbit(x)|$是相同的）。也就是说，此时的森林要求有$m$种不同的树，第$i$种$a_i$棵。首先考虑$m=1$的情况，也就是需要$u$棵同构的树，不难发现这就等同于：

$$\sum _{i=1}^{cn{t}_p}(|S_{p,i}{|}^u{)}^k=\sum _{i=1}^{cn{t}_p}|S_{p,i}{|}^{u\ast k}$$

看上去似乎并未计算过这个式子，为了计算可能需要修改状态。那么先搁置一边，考虑$m>1$的情况，我们能否直接用下面的式子：

$$\begin{array}{}\text{(}\ast \ast \text{)}& \prod _{t=1}^m(\sum _{i=1}^{cn{t}_p}|S_{p,i}{|}^{a_t\ast k})\end{array}$$

计算呢？不可行，因为这并不能排除不同的两组得到同一类树的情况，同时也没有考虑组与组的数目相同时地位等价的问题。

但这样的思考并不是毫无意义的。不难发现，如果组与组之间默认为地位不等，且不同的组可以使用相同的一类树，那么$(\ast \ast )$就是正确的。

最关键的一点是，这两个条件似乎与某一置换下的不动点有异曲同工之妙。我们考虑$f\in G$，则$fix(f)$就是$f$的不动点集合。$f$是由若干个置换环组成的，设有$m^{\prime }$个置换环，并设置换环的大小分别为$a_1^{\prime },a_2^{\prime },\dots ,a_{m^{\prime }}^{\prime }$。可以发现，如果$x$是$f$的不动点，那么有与之前的$a$类似的性质，同一置换环内的位置上，树的种类必须相同。但是，由于置换环本身位置不同，每个置换环就是地位不等的（这也是有序序列的一个好处）。并且，由于我们只要求其为不动点即可，并不需要每个置换环的树种类各不相同，这就完美的符合我们之前的两个条件。

因此我们就可以利用$(\ast \ast )$了，也就是说：

$$\sum _{x\in fix(f)}{\omega }_x=\prod _{t=1}^{m^{\prime }}(\sum _{i=1}^{cn{t}_p}|S_{p,i}{|}^{a_t^{\prime }\ast k})$$

不过还有一个问题没有解决：怎么求$\sum _{i=1}^{cn{t}_p}|S_{p,i}{|}^{a_t^{\prime }\ast k}$？它的形式和$d{p}_p$相似，但是指数增加了$a_t^{\prime }$倍。必须先进一步扩张状态才能解决这个问题。

那么增加一个指标$j$，表示指标扩张的倍数。即：

$$d{p}_{n,j}=\sum _{i=1}^{cn{t}_n}|S_{n,i}{|}^{j\ast k}$$$$tm{p}_{n,j,p}=\sum _{i=1}^{cn{t}_n}[mxs(S_{n,i})\le p]|S_{n,i}{|}^{j\ast k}$$$$f_{p,j,u}=\sum _{i=1}^{cn{t}_{u\ast p+1}}[mns(S_{u\ast p+1,i})=mxs(S_{u\ast p+1,i})=p]|S_{u\ast p+1,i}{|}^{j\ast k}$$

相应修改转移方程：

$$tm{p}_{n,j,p}=\sum _{u=0}^{\lfloor \frac{n-1}{p}\rfloor }{(\genfrac{}{}{0ex}{}{n-1}{u\ast p})}^{j\ast k}tm{p}_{n-u\ast p,j,p-1}\ast f_{p,j,u}$$$$f_{p,j,u}=\frac{(u\ast p){!}^{j\ast k}}{(p!{)}^{u\ast j\ast k}}\ast (\sum _{x\in X}(\prod _{t=1}^m\frac{1}{a_t{!}^{j\ast k}})\ast \frac{{\omega }_x}{|Orbit(x)|})$$

则：

$$\sum _{x\in fix(f)}{\omega }_x=\prod _{t=1}^{m^{\prime }}(\sum _{i=1}^{cn{t}_p}|S_{p,i}{|}^{a_t^{\prime }\ast j\ast k})=\prod _{t=1}^{m^{\prime }}d{p}_{p,a_t^{\prime }\ast j}$$

注意${\omega }_x$也是和$j$相关的。

首先考虑一下状态数量问题，可以发现由于$a_t^{\prime }\le \frac{n}{p}$，因此这两维的乘积不会超过全局的$n$，因此只有$\sum _{i=1}^n\lfloor \frac{n}{i}\rfloor =O(n\log n)$种可能。

还有一个问题是，我们并不只是简单的求$\sum _{x\in X}{\omega }_x$，而是有一个$(\prod _{t=1}^m\frac{1}{a_t{!}^{j\ast k}})\ast \frac{1}{|Orbit(x)|}$的系数，不能这样直接交换求和顺序。

那要通过什么方式转化呢？我们设置换$f$的某个权值为$w_f$，那么有如下等式：

$$\sum _{x\in X}{\omega }_x(\sum _{f\in SG(x)}{w}_f)=\sum _{f\in G}{w}_f(\sum _{x\in fix(f)}{\omega }_x)$$

只是交换了求和顺序，显然成立。这个等式的左边和$\sum _{x\in X}(\prod _{t=1}^m\frac{1}{a_t{!}^{j\ast k}})\ast \frac{{\omega }_x}{|Orbit(x)|}$相似，右边和$\sum _{x\in fix(f)}{\omega }_x$相似，尝试利用这个等式来对目标进行转化。

如果能找到某种权重函数$w$，使得等式：

$$\sum _{f\in SG(x)}{w}_f=C\ast (\prod _{t=1}^m\frac{1}{a_t{!}^{j\ast k}})\ast \frac{1}{|Orbit(x)|}$$

成立，其中$C$是一个常数，那么就有：

$$\sum _{x\in X}(\prod _{t=1}^m\frac{1}{a_t{!}^{j\ast k}})\ast \frac{{\omega }_x}{|Orbit(x)|}=\frac{1}{C}\sum _{x\in X}{\omega }_x(\sum _{f\in SG(x)}{w}_f)$$$$=\frac{1}{C}\sum _{f\in G}{w}_f(\sum _{x\in fix(f)}{\omega }_x)$$$$\begin{array}{}\text{(}\ast \ast \ast \text{)}& =\frac{1}{C}\sum _{f\in G}{w}_f(\prod _{t=1}^{m^{\prime }}d{p}_{p,a_t^{\prime }\ast j})\end{array}$$

由于后方的连乘只和置换环大小情况有关，那么自然也希望权重函数也之和置换环大小有关，而且最好也是连乘形式，即：

$$w_f=\prod _{t=1}^{m^{\prime }}{\tilde{w}}_{a_t^{\prime }}$$

如果可行，那么可以继续转化$(\ast \ast \ast )$式：

$$=\frac{1}{C}\sum _{f\in G}(\prod _{t=1}^{m^{\prime }}{\tilde{w}}_{a_t^{\prime }})\ast (\prod _{t=1}^{m^{\prime }}d{p}_{p,a_t^{\prime }\ast j})$$$$=\frac{1}{C}\sum _{f\in G}(\prod _{t=1}^{m^{\prime }}{\tilde{w}}_{a_t^{\prime }}\ast d{p}_{p,a_t^{\prime }\ast j})$$

则每个置换的结果都只和其置换环分解的大小分布情况有关，可以换一种求和方式，令$h_i={\tilde{w}}_i\ast d{p}_{p,i\ast j}$，枚举置换环的大小分布，并分配标号：

$$=\frac{1}{C}\sum _{f\in G}(\prod _{t=1}^{m^{\prime }}{h}_{a_t^{\prime }})$$$$=\frac{1}{C}\sum _{l>0}\frac{1}{l!}(\sum _{\sum _{t=1}^l{b}_t=u}(\genfrac{}{}{0ex}{}{u}{b_1,b_2,\dots ,b_l})(\prod _{t=1}^l(b_t-1)!)(\prod _{t=1}^l{h}_{b_t}))$$$$=\frac{u!}{C}\sum _{l>0}\frac{1}{l!}(\sum _{\sum _{t=1}^l{b}_t=u}(\prod _{t=1}^l\frac{h_{b_t}}{b_t}))$$

似乎转化为了熟悉的式子。设生成函数$H(x)=\sum _{i>0}\frac{h_i}{i}{x}^i$，那么前面的式子就转化为：

$$=\frac{u!}{C}\sum _{l>0}\frac{1}{l!}(\sum _{\sum _{t=1}^l{b}_t=u}(\prod _{t=1}^l[x^{b_t}]H(x)))$$$$=\frac{u!}{C}\sum _{l>0}\frac{[x^u]H^l(x)}{l!}$$$$=\frac{u!}{C}[x^u]e^{H(x)}$$

好的！也就是说，我们现在有：

$$f_{p,j,u}=\frac{(u\ast p){!}^{j\ast k}}{(p!{)}^{u\ast j\ast k}}\ast (\sum _{x\in X}(\prod _{t=1}^m\frac{1}{a_t{!}^{j\ast k}})\ast \frac{{\omega }_x}{|Orbit(x)|})$$$$=\frac{(u\ast p){!}^{j\ast k}}{(p!{)}^{u\ast j\ast k}}\ast \frac{u!}{C}[x^u]e^{H(x)}$$

唯一的问题就是计算权重函数$\tilde{w}$了。回顾一下，我们是希望满足这个等式：

$$\sum _{f\in SG(x)}{w}_f=\sum _{f\in SG(x)}(\prod _{t=1}^m{\tilde{w}}_{a_t})=C\ast (\prod _{t=1}^m\frac{1}{a_t{!}^{j\ast k}})\ast \frac{1}{|Orbit(x)|}$$

展开$|Orbit(x)|$，即：

$$\sum _{f\in SG(x)}(\prod _{t=1}^m{\tilde{w}}_{a_t})=C\ast (\prod _{t=1}^m\frac{1}{a_t{!}^{j\ast k}})\ast \frac{\prod _{t=1}^m{a}_t!}{u!}$$

对于$x$，它的稳定化子就是满足仅在相同种类树之间进行置换的集合，就是说，只能在同种树内部进行置换环的拆解。那么模仿之前对置换环的枚举方法，换一种方式计算等式左边的值，只是换成了在每一类树内部：

$$=\prod _{t=1}^m(\sum _{l>0}\frac{1}{l!}(\sum _{\sum _{t^{\prime }=1}^l{b}_{t^{\prime }}=a_t}(\genfrac{}{}{0ex}{}{a_t}{b_1,b_2,\dots ,b_l})\ast (\prod _{t^{\prime }=1}^l(b_{t^{\prime }}-1)!)\ast (\prod _{t^{\prime }=1}^l{\tilde{w}}_{b_{t^{\prime }}})))$$$$=\prod _{t=1}^m{a}_t!\ast (\sum _{l>0}\frac{1}{l!}(\sum _{\sum _{t^{\prime }=1}^l{b}_{t^{\prime }}=a_t}(\prod _{t^{\prime }=1}^l\frac{{\tilde{w}}_{b_{t^{\prime }}}}{b_{t^{\prime }}})))$$

同之前，设$W(x)=\sum _{i>0}\frac{{\tilde{w}}_i}{i}{x}^i$，那么上方等式继续转化：

$$=\prod _{t=1}^m{a}_t!\ast [x^{a_t}]e^{W(x)}$$

带回原等式，即为：

$$\prod _{t=1}^m{a}_t!\ast [x^{a_t}]e^{W(x)}=C\ast (\prod _{t=1}^m\frac{1}{a_t{!}^{j\ast k}})\ast \frac{\prod _{t=1}^m{a}_t!}{u!}$$

消去$\prod _{t=1}^m{a}_t!$：

$$\prod _{t=1}^m[x^{a_t}]e^{W(x)}=(\prod _{t=1}^m\frac{1}{a_t{!}^{j\ast k}})\ast \frac{C}{u!}$$

显然我们令$C=u!$，那么有$[x^i]e^{W(x)}=\frac{1}{i{!}^{j\ast k}}$，$e^{W(x)}$就是一个已知的多项式。通过$W(x)=\ln e^{W(x)}$就可以求解出$\tilde{w}$了。

回顾一下过程，可以计算出复杂度是$O(n^2\log n)$。由于多项式$\ln$和$\exp$不是瓶颈，可以用简洁的$O(n^2)$算法来计算。