AT乱做
啥也不会，自闭了，黄队带我飞。
AT评分网站
[ARC057D] 全域木/洛谷/AT
difficulty：3019
根据 kruskal 的过程设计 DP。设 \(f_{V,i,j}\) 表示当前完全图中的各个联通块的大小的可重集为 \(V\)，目前考虑加入的边的权值为 \(i\)，已经钦定好的边导致未被钦定的有 \(j\) 条加入到生成树中不会对答案造成影响。
- 如果当前边未被钦定出现在答案中，那么就不能选这条边，需要从没有影响的 \(j\) 条边中选一个代替它，转移为 \(f_{V,i,j} = j \times f_{V,i + 1,j - 1}\)。
- 如果当前边被钦定要出现在答案中，那么两两枚举目前状态下剩余的连通块，并将他们合并，记枚举的两个连通块大小为 \(x,y\)，那么加入的边有 \(x \times y\) 中选择，并且会多出 \(x \times y - 1\) 条边加入到生成树中不对答案造成影响，转移为 \(f_{V,i,j} =\sum_{x,y \in V | x \neq y} f_{V - \{x\} - \{y\} + \{x + y\},i + 1,j + x \times y - 1}\)。
显然边界为 \(j < 0\) 时取到 \(0\)，\(i > \dfrac{n \times (n - 1)}{2}\) 时取 \(1\)，没有理想的枚举顺序，直接使用记搜记录。submission