2024杭电钉耙1-1003 HDOJ7435 树
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\)