今天热爱数据结构的 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。