U95602 射手座之日

为了报春日抢电脑的一箭之仇，电脑社团的同学向$SOS$团发起了挑战！他们声称：如果$SOS$团可以在新的电脑游戏——$\text{《Sagittarius》}$中取胜，就送给$SOS$团一人一台新式电脑；反之$SOS$团要归还抢走的那台电脑。为了保护电脑中~~学姐换衣服的照片~~，你一定要获胜！

游戏$\text{《Sagittarius》}$是一个多人闯关游戏，游戏有两个组成部分——地图 和关卡表。地图是一个$n$个节点的有根树，每个节点$i$都有权值$x_i$，1号节点 为根；关卡表是一个$\{1, 2, 3, . . . , n\}$的排列$a_i$。每一个回合中，系统会选取关卡表中一段连续的区间$\{a_l, a_{l+1}, \cdots , a_r\}$，设这些节点的$lca$为$k$，则这次游戏胜利的话玩家将会得到$x_k$的收益。如果进行了多次游戏，同一个节点的收益可以被重复获得。春日和你的游戏技术都非常弱，但是$SOS$团中有一个人形自走挂：长门有希。因此你们每次都可以获胜。现在春日想要知道，对于所有不同的回合，你们可以获得的收益之和是多少？

无

无

对于$20\%$的数据，$n \le 100$ 对于$40\%$的数据，$n \le 2000$ 对于$60\%$的数据，$n \le 50000$ 对于另外$20\%$的数据，排列$a_i$是用如下的算法生成的：从一号点始对树 做dfs，到达一个节点的时候输出这个节点。 对于全部数据，$n \le 200000$, $0 \le x_i \le 100000$, $p_i < i$, $a_i$是一个排列。 来自~~毒瘤~~出题人ljt12138。 $upd$：为了尽量卡掉一些$O(nlog^2n)$的做法，我决定把时限从$2s$调到$400ms$ $upd$：把空间从$256MB$改成$64MB$ 数据下载：[戳这里](https://pan.baidu.com/s/1sOyXN_gWBW6dUntwd15f4w?pwd=6n85)