1 条题解
-
0
节点 与其父节点的距离是 cm,其中 是节点 所在子树的质量之和。这个描述很清晰的告诉我们应该树形 DP 得到子树的质量,以及到根的距离。
接下来考虑分析挂一个节点对树的影响。不难发现节点 到根的所有弹簧的距离都增长了 cm,因此对 的影响就只有公共祖先,故增加的距离是
$$\operatorname{dep}(\operatorname{LCA}(x, y)) \times u $$所以是 DP 之后对询问求 LCA 即可。
- 1
信息
- ID
- 65
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者