动态点分治

说实话这题写树剖 $LCT$ 什么的真的思想又不难又好实现的样子，但是我还是选择自虐选择了动态点分治 那就两种做法都稍微提一下： 树链剖分 / $LCT$很容易可以发现一个换根操作只会对当前根在原树（根为 $1$ ）上的祖先一条链造成影响，也就是将它们的子树变成除当前链方向其它与之相连的点集，那么用树剖跳，用线段树维护一下原树上从上面来的和从下面来的，再将所有涉及的节点合并，并且删去算重复的和不该算的即可（虽然我没实现但是这个思路应该是对的 动态点分治首先有两篇博客：zzq、租酥雨 因为我们要算 $\sum\limits_{i = 1}^n s_i^2$ ，可以先想一下 $\sum\limits_{i = 1}^n s_i$ 怎么算，因为每个点的贡献只会被祖先计算到，那么易知 $\sum\limits_{i = 1}^n s_i = \sum\limits_{i = 1}^n value_i * (depth_i + 1)$ ，这个直接用动态点分治维护三个变量 $sumo_i, sumt_i, sumfa_i$ （sumo -> $p$ 子节点权值之和, $sumt$ -> ...