Description:
给你一棵树,每次询问以一个点为根时所有子树点权和的平方和
带修改
Hint:
\(n\le 2*10^5\)
Solution:
这题只要推出式子就很简单了
如果不换根这个平方和树剖直接做就行了
考虑换根的影响了哪些点的贡献
显然只影响了\(1\)到\(u\)的路径上的点
把1到\(u\)这条路径上的点依次标记为\(1,2,3......k\)
我们设\(a_i\)为以1为根时\(i\)的点权和,\(b_i\)为以\(u\)为根的点权和
\(Ans=ans_1-\sum a_i^2 + \sum b_i^2\)
注意到\(a_{i+1}+b_i=sum\)
\(Ans=ans_1-\sum a_i^2 -a_1^2+b_k^2 + \sum (sum-a_{i+1})^2\)
消掉\(\sum a_i^2\)
\(Ans=ans_1-k*sum^2-2*sum*\sum a_i\)
预处理出\(ans1\),每次算一条链就行
(注意最后并没有算\(a_1\))
#include