二分答案(k)
把一个树分成 (m) 个部分,使得 (m) 个部分中的直径不少于 (k).
贪心!
对于一个子树,我们肯定希望有尽可能多的赛道,其次,我们希望子树根节点有一条很长的链.
考虑神奇的递归思想.
如果我们有一棵小树:
O
/
/
O O
O
本质上就是一条链或者是链的结合.
于是我们可以直接维护子树的链.
- 拿出所有子树的顶链
- 贪心地拼接链
- 拿出一条最长的链作为顶链
二分答案(k)
把一个树分成 (m) 个部分,使得 (m) 个部分中的直径不少于 (k).
贪心!
对于一个子树,我们肯定希望有尽可能多的赛道,其次,我们希望子树根节点有一条很长的链.
考虑神奇的递归思想.
如果我们有一棵小树:
O
/
/
O O
O
本质上就是一条链或者是链的结合.
于是我们可以直接维护子树的链.