P12007 【MX-X10-T3】[LSOT-4] 全国联赛？——换根dp+贪心

· · 个人记录

初见思路

显而易见的观察

首先观察到 n-m-1 加上给定的 m 条边就是生成树

挖掘性质

然后考虑两棵树 x,y 合并会对答案产生什么贡献(此时假定树内已经完成)

假定 u,v 是这条边的两端所连端点， u\in x,v\in y ，权值为 w

那么x中的所有点要到 y 中的所有点

每一个条路径都要经过 <u,v> ，所以 w 造成的贡献为 w\times size_x\times size_y

那么此时考虑 x 中的节点，首先要到 v ，再散入到 y 中所有节点

所以此时贡献为

w\times size_x\times size_y+size_x\times dp_y+size_y\times dp_x #### dp更新问题 我们发现要找到 $x$ 中 $dp$ 最小的点进行维护 合并的过程中可以动态维护，两个连通块间连边的时候肯定连这个点 那么当这两个点相连时，两边各自的 $dp$ 值如何变化呢 $$dp_u=dp_u+dp_v+w\times size_y$$ $$dp_v=dp_u+dp_v+w\times size_x$$ 那么显然是所在连通块大的大了 #### 合并顺序 让小的边尽量参与到经过次数多的路径中 所以小的边先合并，每次合并并头两大的(原因也在前面的dp那块) 用大根堆维护 #### 初始化 **初始时连边是不听你的，所以重心不能动态维护** 树形dp+换根dp预处理即可 算初始状态对答案的贡献要用乘法逆元 记得开long long