本文从WordPress迁移而来, 查看全部WordPress迁移文章
树dp (树上的一些性质)
题意:将树上的每一个点移动到另一个点的位置(但不一定是两两点交换),每个点移动走过的距离累加起来得到一个和,使得这个和最大。
这题不是很想归类为树dp,因为主要不依靠父子关系来得到想要的信息,这题主要是根据题意来搞清楚一个性质并且证明它,那么就是一个很容易实现代码的题目了
性质:找任意一条边,都能将整个树分为两个部分,左部有m1个点,右部有m2个点,假设较小值为m1,那么在整个移动过程中,这条边,被走过的次数就是2 * m1。
简单的证明,如果树的点数n为偶数,一定能找到一条边,使得左部和右部的点数均为n/2,那么只要把左部和右部的点一一对应交换,那么这条边就一定被走过了2 * n/2次,和上面的结论符合
如果点数n为奇数(n>=3,n=1的情况不需要讨论嘛都不能交换),一定能找到一条边,左部的点数为n/2,右部点数为n/2+1,将左部的点和右部的n/2个点一一对应交换,那么这条边就一定能走过2 * n/2,至于右部还有1个点没有交换,只要将该点和此时右部中的一个点交换即可
所以问题转化为,枚举每条边,找出它左部和右部中点数的较小值m,这条被走过的次数就是2 m,产生的价值自然是2 m * w,再将左右边产生的价值累计即可
1 |
|