题解 P3676 【小清新数据结构题】

· · 题解

感觉最小清新的其实是这个数据结构题啊，链剖直接暴力讨论一波就艹过去了好气啊，下面来讲一种比较容易work全是板子的O(nlogn)做法。

首先我们发现有一个良心30分部分分，每次询问根都为1，这个要怎么搞呢？

我们的要求就是把一个点到根的路径上的子树和全部加上一个值，询问所有点子树平方和。

考虑对一个点x点权+y对答案的贡献，我们发现对于每个x的父亲f，假设原来点权和为p，现在就变成了p+y，那么对答案贡献就是(p+y)^2-p^2=2py+y^2，我们只要统计x到根的点权和即可。

那么我们只要支持将一个点到根的路径点权加上一个数和统计一个点到根的点权和，直接树链剖分就可以做到两个log，当然如果你追求理论复杂度那么用lct就可以做到一个log。

现在考虑满分，我们发现这个平方十分麻烦，不妨考虑如果没有平方怎么做，即要以点p为根考虑整棵树，求出每个点子树的点权和，直接加在一起。

考虑一个点s的点权v_s只有它及祖先才会计入，即计入了dis(s,p)+1次，那么没有平方的答案就是\sum_{i=1}^n dis(p,i)v_i+\sum_{i=1}^n v_i，这个东西显然是可以用动态点分治维护的，参见bzoj3924。

现在问题就是这个平方，我们设s_x为x子树的点权和，w为点权总和，那么我们可以发现\sum_{i=1}^n s_i(w-s_i)无论根是啥都是一个定值。

证明十分简单，考虑对于每对点(i,j)，在i到j的路径上每条边都加上v_iv_j的权值，那么i往父亲边权的就是s_i(w-s_i)，因为要在自己子树中选一个点权，外面选一个，显然加在一起值不会变。

那么我们在1为根的时候求出\sum_{i=1}^n s_iw-s_i^2，然后在p为根时求出\sum_{i=1}^n s_i，把\sum_{i=1}^n s_i^2解出来即可。