信息
- ID
- 2671
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 7
- 标签
- (无)
- 递交数
- 5
- 已通过
- 4
- 上传者
对于每次修改,按照题意暴力遍历整棵树计算答案可得 60pt。
设 f 为 u 的父节点,T(u) 表示以 u 为根的子树。
通过简单的模拟样例,容易注意到:T(f)−T(u) 中除 f 之外的所有点会乘上一个常数,T(u) 中除 u 之外的点会乘上另一个常数。
至于乘上什么常数,通过模拟样例应该很容易知道,请勿偷懒。
那么就可以利用子树内 dfn 连续的特性,先修改 T(f), 再修改 T(u), 最后单点修改 u 的 a 值,对应 dfn 上的三个区间,可使用线段树维护。

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