题解 |#Diameter Counting#

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

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

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

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

如果直接处理的值，会遇到重复的问题，因此我们考虑容斥，先求出点数为深度小于等于的数量，然后可以得到

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

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

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

求出后，我们就可以通过和分类讨论求得答案，对于一个长度为的直径，设，分为两种情况：

• 为奇数，则整棵树可被从中间直接分成两棵深度为的带标号有根树，我们直接取1号节点所在有根树计数即可，数量为
• 为偶数，将直径中点视为当前树根，则答案即为根节点连接着大于等于两个深度为的子树的树的数量，我们可以用所有深度为的带标号有根树数量，减去仅有一个深度为的子树的树的数量，计数时直接枚举该子树即可，数量为

最终答案为每种直径的数量乘长度之和，直接dp复杂度为