【五校联考2015 9.5】送你一棵线段树

题目大意

你有 n 棵树。每一棵树的形态如下给出：

• 0号树 T0 只有一个点，标号为0
• 对于第 i 棵树 Ti(i>0) ，它通过拷贝第 Ai 和 Bi 棵树，并将对应原树上的 Ci 号和 Di 号节点链接一条 Li 的边得到。并且新树上原本属于 Bi 节点的节点标号都加上了 sizeAi 。

现在要求你计算每一棵树的这个值

∑i∈Ti∑j∈Tidis(i,j)

其中 dis(i,j) 表示树上点 i 和点 j 之间的最短路的长度。

n<60,Ai<i,Bi<i,Case<100

---

分析

不难发现最坏情况下， sizeTn 是可以达到 2n 的。
我们先想一下如果我们要计算一棵树的答案需要知道些什么，很自然可以想到从这棵树的构成出发。它等于 Ai 的答案加上 Bi 的答案再加上跨过 Ai 和 Bi 的所有路径的长度，前两部分可以递归地算，主要是看后一部分。

后一部分显然等于

sizeAisumDi+sizeBisumCi+LisizeAisizeBi

size 数组很好统计，主要是看如何计算 sum 。
考虑到每棵树上直接需要查询 sum 值的点顶多只有 n 个，间接需要查询（即后面的树上的某个点属于前面某棵树上的点，我们依旧需要把它算出）的点顶多只有 n2 个。
那么依照前面的思路，我们拆成两棵树来分别维护这些关键点的 sum 值，假设 x 是 Ti 的关键点且 x∈TAi （ x∈TBi 是同理的）。

sumTi,x=sumAi,x+[dis(Ci,x)+Li]sizeBi

那么新的问题就出现了，我们还有维护关键点之间的 dis 值。其实思路是同理的，就略推导的式子了。

最终的时间复杂度 O(n3Case)