小清新数据结构题
非常清新的好题
题意
我因为没读懂题卡了一天
维护两个操作
-
改点权
-
查询以 \(u\) 为根时所有子树点权和的平方
也就是 \(\sum s_u^2\)
思路
首先这里的根在不断换
考虑换根
先以1为根求出 \(A = \sum s_u^2\)
-
改点权
显然在 \(u\) 到根的路径上的 \(s\) 都会受影响
也就是 \(s \to (s + \Delta) ^ 2\)，拆开变成 \(s^2 + \Delta^2 + 2 \times s \times \Delta\)
这个增量是在路径上的每个节点的增量
\(s\) 没有变化， 于是 \(ans_r = A + dep_r \cdot S^2 + 2S \cdot \text{pathsum}(1\to r)\)
-
查询
设路径为：\(v_0 = 1, v_1, v_2, ..., v_k = r\)，其中 \(k\) 是从1到r的边数。
对于路径上的节点：
-
新根 \(r\)：包含所有节点
\[s2_r = S \] -
其他节点 \(v_i (0 \le i < k)\)：
- 以1为根时：\(v_{i+1}\) 在 \(v_i\) 的子树中
- 以 \(r\) 为根时：\(v_i\) 在 \(v_{i+1}\) 的子树外
\[s2_{v_i} = S - s_{v_{i+1}} \]所以
\[ans_r - A =\sum_{u} (s2_u^2 - s_u^2) \]关注右边的式子
对于 \(r\)
\[s2_r^2 - s_r^2 = S^2 - s_r^2 \]其他 \(v_i\)
\[s2_{v_i}^2 - s_{v_i}^2 = (S - s_{v_{i+1}})^2 - s_{v_i}^2 \]所以
\[ans_r - A = \sum_{i=0}^{k-1} \left[(S - s_{v_{i+1}})^2 - s_{v_i}^2\right] + (S^2 - s_r^2) \]展开
\[= \sum_{i=0}^{k-1} \left[S^2 - 2S s_{v_{i+1}} + s_{v_{i+1}}^2 - s_{v_i}^2\right] + S^2 - s_r^2 \]\[= (k+1)S^2 - 2S \sum_{i=0}^{k-1} s_{v_{i+1}} + \sum_{i=0}^{k-1} (s_{v_{i+1}}^2 - s_{v_i}^2) - s_r^2 \]对于第二项进行化简
\[\sum_{i=0}^{k-1} (s_{v_{i+1}}^2 - s_{v_i}^2) = s_r^2 - s_1^2 \]带入
\[ans_r - A = (k+1)S^2 - 2S \sum_{i=1}^k s_{v_i} + (s_r^2 - s_1^2) - s_r^2 \]\[= (k+1)S^2 - 2S \sum_{i=1}^k s_{v_i} - s_1^2 \]又\(s_1=S\)
所以
\[ans_r - A = k\times S^2 - 2S \sum_{i=1}^k s_{v_i} \]注意，这里的 \(k\) 其实上是 \(dep_r + 1\)
也就是
\[ans_r = A + (dep_r + 1) \times S^2 - pathsum(1 \to r) \times 2s \]
-
有了这两个式子
点分树或者树链剖分维护路径点权和即可
应该不需要代码了吧