1 条题解

  • 1
    @ 2026-6-17 10:49:17

    对于每次修改,按照题意暴力遍历整棵树计算答案可得 60pt60pt。

    设 ff 为 uu 的父节点,T(u)T(u) 表示以 uu 为根的子树。

    通过简单的模拟样例,容易注意到:T(f)−T(u)T(f) - T(u) 中除 ff 之外的所有点会乘上一个常数,T(u)T(u) 中除 uu 之外的点会乘上另一个常数。

    至于乘上什么常数,通过模拟样例应该很容易知道,请勿偷懒。

    那么就可以利用子树内 dfndfn 连续的特性,先修改 T(f)T(f), 再修改 T(u)T(u), 最后单点修改 uu 的 aa 值,对应 dfndfn 上的三个区间,可使用线段树维护。

    本题下手容易,思路平滑,考察的基础知识点较丰富,是一道非常不错的训练题。

    • 1

    信息

    ID
    2671
    时间
    1000ms
    内存
    512MiB
    难度
    7
    标签
    (无)
    递交数
    5
    已通过
    4
    上传者