1 条题解

  • 0
    @ 2022-11-18 23:08:05

    节点 xx 与其父节点的距离是 1+wx1 + w_x cm,其中 wxw_x 是节点 xx 所在子树的质量之和。这个描述很清晰的告诉我们应该树形 DP 得到子树的质量,以及到根的距离。

    接下来考虑分析挂一个节点对树的影响。不难发现节点 xx 到根的所有弹簧的距离都增长了 uu cm,因此对 yy 的影响就只有公共祖先,故增加的距离是

    $$\operatorname{dep}(\operatorname{LCA}(x, y)) \times u $$

    所以是 DP 之后对询问求 LCA 即可。

    这里是代码

    • 1

    信息

    ID
    65
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    2
    已通过
    1
    上传者