P11477 [COCI 2024/2025 #3] 林卡树 / Stablo

译自 [COCI 2024/2025 #3](https://hsin.hr/coci/) T4。$\texttt{2s,0.5G}$。满分为 $120$。

给定 $n$ 个节点的有根树，根节点为 $1$。点 $i$ 的点权为 $v_i$。 定义函数 $$f(y)=\sum_{x\in \operatorname{subtree}(y)} \operatorname{dist}(x,y)\cdot v_x$$ 其中，$\operatorname{subtree}(y)$ 表示 $y$ 的子树内所有点构成的集合（包括 $y$），$\operatorname{dist}(x,y)$ 表示 $x,y$ 之间的最短路径上的边数。换言之，$f(y)$ 是 $y$ 子树内所有点的点权乘以到 $y$ 的距离求和。 有 $q$ 次操作，每次操作给定两个节点 $x,y$。在一次操作中： - 将 $x$ 的所有儿子接到 $x$ 的父亲上； - 将 $x$ 删掉； - 令 $y$ 的儿子中，包含 $x$ 的为 $z$。将 $x$ 插入到 $y$ 和 $z$ 之间。 - 求出 $f(y)$。 保证 $x\in \operatorname{subtree}(y)$，且 $x\neq y$。特别地，若 $y$ 是 $x$ 的父亲，则原树的形态保持不变。 需要注意的是，**操作之间相互独立**。也就是说，每次操作都是在初始形态的树上操作（而不是在上一次操作的基础上操作）。

无

无

### 样例解释 样例 $1$ 中，操作后，有 $\operatorname{dist}(1,3)=1,\operatorname{dist}(1,2)=2$。所求为 $3+2\cdot 2=7$。 ### 数据范围 对于 $100\%$ 的数据，保证： - $1\le n,q\le 5\times 10^5$； - $1\le v_i\le 10^6$； - $1\le p_i\lt i$； - $1\le x,y\in n$； - $x\neq y$，$x\in \operatorname{subtree}(y)$。 | 子任务编号 | $n,q\le$ | 特殊性质 | 得分 | | :--: | :--: | :--: |:--: | | $ 1 $ | $10^3$ | | $ 21 $ | | $ 2 $ | $5\times 10^5$ | A | $ 37 $ | | $ 3 $ | $5\times 10^5$ | B | $ 22 $ | | $ 4 $ | $5\times 10^5$ | | $ 40 $ | - 特殊性质 A：树的形态是链。换言之，$p_i=i-1$。 - 特殊性质 B：每个节点最多有 $20$ 个儿子。