date: 2020-07-27 12:00~17:00

2020牛客暑期多校训练营（第六场）

签到题，只有 $1,24$ 满足要求。

题目大意：定义一个森林的价值为所有点的度数平方和。求所有 $n$ 个点带标号的森林的价值和。

题解：首先求树的价值平方和。注意到一个点的度数等于 prufer 序列中出现次数加 $1$，且每个点的贡献相同，因而是 $n\cdot\sum_{i=0}^{n-2}(i+1)^{2}{n-2\choose i}$。森林 dp 一下即可。