加一个超级根，解决prufer序列有根树问题。现在问题变成 个节点，超级根节点的儿子数量为 的所有标号树的权值和。令 表示i节点的儿子个数。那么 的权值有两种。第一种是 ，表示被分成了 段，相邻两端中间包着一个儿子。第二种是 ，表示被分成了 段，每段后面接着一个儿子。若所有都采取第一种分段，一共会得到 段，而希望的段数是 段。每将一个节点的分段方式从第一种变成第二种，就会少一段。因此需要将 个节点从第一种分段方式变成第二种。考虑一个节点的儿子个数是 ，也就是说他会在长度为 的prufer序列中出现 次（度数为 ，出现度数减一次）。那么权值为 ，其中 为 或 。又因为儿子之间的顺序任意，所以价值...