题解-直径和

A shoulder for the past

直径和

求 $n$ 个点的有标号无根树的直径之和

Solution:

基础思想是找到直径中点拼起来

假设我们能 dp 出来深度为 $j$ 大小为 $i$ 的树和森林的个数

对于奇数的只需要取中间的边就能把树分成两个部分，枚举两个部分的大小即可

偶数需要容斥，取直径的中点，他至少要有两个子树深度为 $\dfrac{d}{2}-1$ 先算存在的，然后枚举大小减去有一个不合法的

具体而言 设 $f_{i,j}$ 表示 $i$ 个点 深度至多为 $j$ 的树个数 ,$g_{i.j}$ 表示 $i$ 个点，深度至多为 $j$ 的森林个数

$h_{i,j}$ 表示 $i$ 个点 深度为 $j$ 的树个数

转移有 $f_{i,j} \gets g_{i,j-1} \times i$ 选定根

$g_{i,j} = \sum \binom{i-1}{k-1} f_{k,j}g_{i-k,j}$ 加上一个新树（注意标号）

奇数直径为 $\sum \binom{n-1}{i-1}h_{i,d}\times h_{n-i,d}$ ，偶数为 $h_{n,d}-\sum \binom{n}{i}h_{i,d-1}\times f_{n-i,d-1}$