Problem E. Shaass the Great

Brief description:

。。。给定一颗边权树。。你可以移动任意一条边。。只要新图仍然是一颗树。。
。。。最小化。所有点对之间的距离的和。
(。。n = 5000。。。)
ゆっくり読んでください ...

A. 略。
B. idfs() 或者 bfs() 均可。
C. 组合 DP。
。。首先忽略同组之间的差异。。那么最后就是乘以一堆阶乘。。这里记作 pi 。。。
。。然后 f[i] 表示当前有 i 个粘着点时的方案数。。。
。。那么转移就是枚举上回的粘着点、本回分成多少组以及破坏了上回多少个粘着点。。。
。。复杂度 O(n^4)。。（450*50*50*50）。。。
D. 做法有很多。。个人比较倾向暴力矩形切割。。。
E. 裸 AC 自动机 DP。。。

代码。。
https://github.com/lychees/Exercise/tree/master/Online%20Contest/%E7%AC%AC%E4%BA%8C%E5%B1%8A%E8%85%BE%E8%AE%AF%E7%BC%96%E7%A8%8B%E9%A9%AC%E6%8B%89%E6%9D%BE/%E5%A4%8D%E8%B5%9B