题解 |#Diameter Counting#

D：
题目大意：求所有n个点带标号树的直径总和

经典题，参考jzoj2755-[2012东莞市选]树的计数（做过原题却一直没想起来的我是屑）

首先考虑对于每一棵树，如何计数才能避免重复的问题。容易发现，树的直径上位于正中的点或边永远只有一个，因此我们可以直接依据直径的中点或中间的边计数。

我们沿着树直径中点将其分为两个部分，容易发现，此时可以忽略其他信息，和答案相关的信息只有每个部分有根树的深度，因此我们可以先处理点数为 $n$ ，深度为 $d$ 的带标号有根树的数量，设为 $F_{n,d}$

如果直接处理 $F_{n,d}$ 的值，会遇到重复的问题，因此我们考虑容斥，先求出点数为 $n$ 深度小于等于 $d$ 的数量 $G_{n,d}$ ，然后可以得到 $F_{n,d}=G_{n,d}-G_{n,d-1}$

对 $G$ 进行转移的过程中，为了保证不重复计算，我们每次枚举一棵包含除根节点以外 $id$ 最小的点的子树，这样子树的转移就是唯一的，转移方程为:

$G_{i,j}=\sum_{x=1}^{i-1}{G_{x,j-1}G_{i-x,j}\binom{i-2}{x-1}\frac{i}{i-x}}$

这里的系数较为特殊，是因为我们取的特征节点为除根节点以外的最小节点，因此根节点要单独处理，先将原本 $G_{i-x,j}$ 中包含的根节点标号的影响消除，再为根节点重新选一个标号，事实上，为了转移方便，我们可以对式子进行转化：

$\frac{G_{i,j}}{i}=\sum_{x=1}^{i-1}{\frac{G_{x,j-1}}{x}\frac{G_{i-x,j}}{i-x}\binom{i-2}{x-1}x}$

全部转移完再乘系数求出 $G$ ，从实际含义上看，我们可以把此处 $\frac{G_{i,j}}{i}$ 视为 $i$ 个节点除了根节点以外所有节点都带标号的有根树数量，这种含义推出来的转移和上面的式子相同

求出 $F，G$ 后，我们就可以通过 $F$ 和 $G$ 分类讨论求得答案，对于一个长度为 $len$ 的直径，设 $d=\lfloor len/2\rfloor$ ，分为两种情况：

$len$ 为奇数，则整棵树可被从中间直接分成两棵深度为 $d$ 的带标号有根树，我们直接取1号节点所在有根树计数即可，数量为 $\sum_{i=1}^{n-1}{F_{i,d}F_{n-i,d}}\binom{n-1}{i-1}$
$len$ 为偶数，将直径中点视为当前树根，则答案即为根节点连接着大于等于两个深度为 $d-1$ 的子树的树的数量，我们可以用所有深度为 $d$ 的带标号有根树数量，减去仅有一个深度为 $d-1$ 的子树的树的数量，计数时直接枚举该子树即可，数量为 $F_{n,d}-\sum_{i=1}^{n-1}F_{i,d-1}G_{n-i,d-1}\binom{n}{i}$

最终答案为每种直径的数量乘长度之和，直接dp复杂度为 $O(n^3)$