题解 - Luogu P3676 小清新数据结构题
点分树是什么/yiw
定义 \(s_i\) 为 \(i\) 子树内的权值和，默认 \(1\) 为根
首先考虑没有换根的解法
考虑把点权变换转化为加上一个数，即 \(val_{x}\leftarrow y\) 转化为 \(val_{x}\leftarrow val_{x} + (y - val_{x})\)
定义这个加上的数为 \(z\)，考虑加上 \(z\) 对答案有什么影响
不难发现只会对 \(i \in \operatorname{path}(1, x)\) 上的 \(s_i\leftarrow s_i + z\)
所以多的贡献即为：
\(\sum\limits_{i = {path}(1, x)} (s_{i} + z)^2 - \sum\limits_{i = {path}(1, x)} s_{i}^2 = \sum\limits_{i = {path}(1, x)} (s_i^2 + 2s_i z + z^2) - \sum\limits_{i = {path}(1, x)} s_{i}^2 = \sum\limits_{i = {path}(1, x)} (2s_i z + z^2) = \operatorname{len}(\operatorname{path}(1, x)) z^2 + 2z\sum\limits_{i = {path}(1, x)} s_i\)
这个式子很明显树剖就行了
答案的初始值即为 \(\sum\limits_{i = 1}^n s_i^2\)，每次修改加上对应的贡献即可
考虑有换根怎么做
则不难发现会改变的还是 \(i \in \operatorname{path}(1, x)\) 上的点
令 \(k = \operatorname{len}(\operatorname{path}(1, x))\)，\(a_i,b_i\) 为 \(\operatorname{path}(1\to x)\) 上的 \(k\) 个点依次排列，其分别以 \(1,x\) 为根的 \(s\) 的值
然后能发现一个性质，\(a_{i + 1} + b_{i} = s_1 = a_1 = b_k\)，因为在树上这两部分正好拼成了整个树，而 \(a_1,b_k\) 都是整个树
然后算贡献：
\(-\sum\limits_{i = 1}^k a_i^2 + \sum\limits_{i = 1}^k b_i^2 = -a_1^2 - \sum\limits_{i = 2}^k a_i^2 + \sum\limits_{i = 1}^{k - 1} (s_1 - a_{i + 1})^2 + b_k^2 = \sum\limits_{i = 2}^k a_i^2 + \sum\limits_{i = 2}^{k} (s_1 - a_i)^2 = \sum\limits_{i = 2}^k a_i^2 + \sum\limits_{i = 2}^{k} (s_1^2 - 2s_1a_i + a_i^2) = \sum\limits_{i = 2}^k (s_1^2 - 2s_1a_i) = (k - 1)s1^2 - 2s_1\sum\limits_{i = 2}^k a_i = (k + 1)s1^2 - 2s_1\sum\limits_{i = 1}^k a_i\)
所以 \(ans\) 加上这部分贡献就是答案啦