传送门：http://acm.hdu.edu.cn/showproblem.php?pid=6769
题目大意：给你一棵树，每条边有两种权值a,b.让你从里面选出k条a,n - k - 1条b.使得整棵树的直径最小.
题目思路:
让我们最小化直径。直径又是树的最大路径。那么就是最小化最大值。自然可以想到二分答案。
其实也是:要保证整棵树的直径最小。如果直接dp的话，你无法保证经过每个点的最长路径都是最小的。
我们的目标是要一个整体最小化，但是dp无法做到.不过如果已知一个直径长度A。那么我们dp要做的就从 [最小化答案] 变成了 [寻找可行解].直径这个变量就从 [目标函数] 变成了 [限制条件] 。我们只要保证经过每个点的最长路径不超过A即可.
然后考虑
直接套树形背包即可.
注意：
1.那么转移的时候:初始化为无解，当且仅当 之前的最长链与该子树的最长链拼接起来 <= mid时，才可以转移.
2.sz[u]代表着边的个数而不是点的个数了.
关键代码
京公网安备 11010502036488号