Problem - 7097

今天热爱数据结构的 mengxin 回想起 TA 刚学线段树时遇到的一道有趣的数据结构题：

给定一棵很大很大的树，由于这棵树太大了，它按照这样的方式输入：

- 初始树上只有 1 个点，编号为 $0$；
- 依次对树进行 $m$ 次操作，第 $i(1 \leq i \leq m)$ 次操作给出整数 $p_i,l_i$，新加入 $l_i$ 个节点并将它们和 $p_i$ 用 $l_i$ 条边串成一条链，使得这条链的一端编号为 $p_i$。设这条链的另一端编号为 $i$，新加入的其他节点没有编号。

$m,p_i,l_i$ 均在输入中给出，同时给出一个长度为 $n$ 的整数序列 $a_1,a_2,\cdots,a_n$，其中 $a_i \in [0,m]$，你需要设计一个数据结构支持：给出序列中的一段区间 $[l,r]$，快速计算 $\sum_{i=l}^r \sum_{j=l}^r \mathrm{dist(a_i,a_j)}$ 的值，其中 $\mathrm{dist}(x,y)$ 表示 $x$ 与 $y$ 在树上的唯一路径经过的边数。

由于当时的 mengxin 只会线段树，甚至求树上距离也只会暴跳，即对于两个点$u, v$，花费$\mathrm{dist}(u,v)$代价求出它们的距离。所以 mengxin 想通过建立线段树解决该问题。具体地，mengxin 将会用以下递归方法对于序列上的区间 $[1,n]$ 建立一棵线段树：

1. 通过 $\sum_{i=1}^n \sum_{j=1}^n \mathrm{dist}(a_i,a_j)$ 次暴跳操作计算当前线段树节点对应的答案；
2. 如果区间长度为 1 退出递归过程；
3. 否则选择 $\mathrm{mid} \in [1,n-1]$，递归对 $[1,\mathrm{mid}]$ 和 $[\mathrm{mid}+1,n]$ 建立线段树。

虽然现在 mengxin 意识到这样无法正确得到答案，同时 TA 已经可以熟练地使用 top cluster 和二次离线莫队秒杀该题，但 TA 似乎还想解决曾经的疑惑：应该如何选择线段树上每个区间的 $\mathrm{mid}$ 使得建立线段树的过程中暴跳次数尽可能少呢？

mengxin 花了 $10^{-40}$ 秒解决了本题，但毒瘤的 mengxin 还想加强一下：称初始序列为第 $0$ 个版本，接下来 mengxin 会给出 $r$ 个版本，第 $i(1 \leq i \leq r)$ 个版本是通过在第 $q_i$ 个版本的序列末尾加入一个元素 $x$ 得到的。注意新增第 $i$ 个版本对第 $q_i$ 个版本没有影响。mengxin 想知道每个版本的答案，但这下 TA 不会做了，所以 TA 找到了聪明智慧的你来帮帮 TA。

本题有多组测试数据。

第一行一个整数 $T(1 \leq T \leq 10)$ 表示测试数据组数。

每组测试数据第一行三个整数 $m,n,r(1 \leq m,n \leq 1500, 0 \leq r \leq 300)$ 分别表示建树进行的操作次数，序列的长度和操作序列的次数。

接下来 $m$ 行，第 $i$ 行两个整数 $p_i,l_i(0 \leq p_i \leq i-1, 1 \leq l_i \leq 10^7)$ 描述一次操作。

接下来一行 $n$ 个整数 $a_1,a_2,\cdots,a_n(0 \leq a_i \leq m)$ 描述初始序列。

接下来 $r$ 行，第 $i$ 行两个整数 $q_i , x_i(0 \leq q_i \leq i-1, 0 \leq x \leq m)$ 描述一个版本。

Just a Data Structure Problem