10 22

• 9.3
  • 直径问题：考虑中心
  • 进行操作之后
    • 中心在点上
      • 枚举中心 \(x\)
      • 对于所有点 \(x\) 直径 <= 距离 \(x\) 最远点的距离乘二
      • 而直径则是等于距离中心最远点的距离乘二
      • 我们可以考虑一开始的直径为 \(2 \cdot R\) 则当最后的 \(max(dist) <= R+P\) 的时候最多可以操作 \(R \cdot leaf - \sum_{y \in leaf} D_y + P \codt leaf\)
      • 可以用这个 \(C + P \cdot k\) 来更新 \(dp_{R+P}\) 的 \(\max\)
      • 可以发现它们都是直线，并且斜率是统一的（因为我们不可能选一个叶子作为中心），故我们可以维护 \(<=n\) 的答案，后面的取最大值即可
  • 中心在边上
    • 枚举边在 \(x,y\)，这条边的长度一定是 1，并且中心在终点处
    • 故 \(R = k + 0.5\)
    • \(x\) 这一侧离 \(x\) 的最远距离为 \(R_1\)，\(y\) 这一侧离 \(y\) 的最远距离为 \(R_2\)
    • 故 \(R = \max{R_1,R_2} + 0.5\)
    • 与上述情况大差不差