小清新数据结构题

小清新数据结构题

动态点分治!

题目叙述

小清新数据结构题
有一棵$n$个点的树,每个点有一个点权。现在有$q$次操作,每次操作是修改一个点的点权或指定一个点,询问以这个点为根时每棵子树点权和的平方和。

题解

这根本不是路径问题啊,这是子树的问题!点分治无法解决!所以,如何变成路径问题?

这个其实相当于$\sum_{i=1}^n\sum_{j=1}^nv_iv_j\operatorname {dep}(\operatorname{lca}(i,j))$。

那么,大概把一个点当成LCA计算低下的点的贡献和?这好像不太靠谱,因为无法带修改。

考虑化简这个式子:

$$
\begin{aligned}
\sum_{i=1}^n\sum_{j=1}^nv_iv_j\operatorname {dep}(\operatorname{lca}(i,j)) &= \frac{1}{2}\sum_{i=1}^n\sum_{j=1}^nv_iv_j(\operatorname {dep}(i)+\operatorname {dep}(j)-2\operatorname {dis}(i,j))
\end{aligned}
$$

可以把式子拆成两个部分:
$2\sum_{i=1}^n\sum_{j=1}^nv_iv_j\operatorname{dep}(j)=2(\sum_{i=1}^nv_i)(\sum_{i=1}^nv_j\operatorname{dep}(j))$和$\sum_{i=1}^n\sum_{j=1}^n2v_iv_j\operatorname{dis}(i,j)$

对于第一个,可以把$\operatorname{dep}(i)$看作到根节点的距离。

于是可以发现第二个和第一个都是类似于$\sum_{j=1}^n\operatorname{dis}(i,j)v_j$这样的式子。显然可以动态点分治维护。

代码

Tagged with:

发表评论