Problem
给一棵根为 1 的有根树，点 $i$ 具有一个权值 $A_i$ 。
定义一个点对的值 $f(u, v)=\max \left(A_u, A_v\right) \times\left|A_u-A_v\right|$ 。
你需要对于每个节点 $i$ ，计算 $a n s_i=\sum_{u \in \operatorname{subtree}(i), v \in \operatorname{subtree}(i)} f(u, v)$ ，其中 $\operatorname{subtree}(i)$ 表示 $i$ 的子树。
请你输出 $\oplus\left(a n s_i \bmod 2^{64}\right)$ ，其中 $\oplus$ 表示 XOR。
$n \leq 5 \times 10^5, 1 \leq A_i \leq 10^6$
Solution
先来愉快的推式子。
其实 $\max \left(A_u, A_v\right) \times\left|A_u-A_v\right|$ 其实就是 $\max^2-\max \cdot \min$，这两部分可以分开思考。
对于 $\max\cdot\min$，其实就是在 $i$ 的子树内任选两个点 $u,v\in \operatorname{subtree}(i)$ 相乘
对于 $\max ^2$，也就是 $\sum_{u,v\in \operatorname{subtree}(i)}(\max(A_u,A_v))^2$，我们需要思考子树合并的情况。
假设我们已经计算了节点 $u$ 的所有子节点的子树的内部信息，$v$ 是 $u$ 的某个儿子，此时我们需要计算
- $u$ 与 $\operatorname{subtree}(v)$ 之间的贡献
- $\operatorname{subtree}(v_i)$ 与 $\operatorname{subtree}(v_j)$ 之间的贡献（即跨点 $u$ 的两点之间的贡献）
我们按照以下方式合并的同时计算贡献（以下步骤来自于题解）
- $\operatorname{subtree}(u)$ 初始为 $\{u\}$ 。
- 计算 $\operatorname{subtree}(v)$ 和当前 $\operatorname{subtree}(u)$ 之间点对的答案。（跨越 $u$ 节点的部分）。
- 把 $\operatorname{subtree}(v)$ 子树内的答案直接累加。（不跨越 $u$ 节点的部分）。
- $\operatorname{subtree}(u) \leftarrow \operatorname{subtree}(u)+\operatorname{subtree}(v)$ （将 $v$ 的子树加入到 $u$ 中）。
我们需要维护两个变量：一个子树内的权值出现次数 $cnt$ 与权值平方和 $sum$。
当前子树 $\operatorname{subtree}(u)$ 内加入一个权重为 $w$ 的点，对于答案贡献多少呢？
对于 $\operatorname{subtree}(u)$ 中每个权值小于 $w$ 的点，贡献 $1\times w^2$，总计 $2\times\sum_{i=1}^{w-1} cnt_i\times w^2$。
对于 $\operatorname{subtree}(u)$ 中每个权值大于等于 $w$ 的点（权重为 $w^\prime$），贡献 $1\times {w^\prime}^2$，总计 $2\times\sum_{i=w}^{10^6}sum_i$
对于每个节点，我们开一颗线段树。初始时，每个节点的线段树只包含其本身点权。计算完某个点所有儿子的 $ans$ 之后，我们将所有儿子的线段树合并到其自己上，同时计算贡献。
Code
1 |
|
COMMENTS
via giscus