一些虚树练习

P4103
看到\(\sum k \leq n\)直接想到建虚树\(dp\)
\(mi_i = min \lbrace dep_v - dep_i \rbrace\)
\(mx_i = max \lbrace dep_v-dep_i\rbrace\)
\(sum_i = \sum dep_v-dep_i\)
\(siz_i\)表示\(i\)的子树内关键点的数量
先处理\(ans_{max}，ans_{min}\)
可以发现，两个关键点之间的距离会跨越根节点.

蓝色的就是这一条边的长度，不妨拆成两部分。

紫色与棕色的两部分可以在分别的子树中处理出来，考虑如何合并子树的信息。
假设现在枚举到的子节点编号为\(v_i\),则在遍历这个子节点前我们处理了\(v_1 \dots v_{i-1}\)合并后的信息。
记最终答案分别为\(ans_{max},ans_{min},ans_{sum}\)，\(dep_{v_i}-dep_u=l\)
那么前\(i-1\)个子节点都可以与第\(i\)个子节点的信息进行合并。以处理\(ans_{min}\)为例。
目前我们已知根据前\(i-1\)个子节点的\(ans_{min}\)与根据前\(i-1\)个子节点合并得出的\(mi_u\)
则前\(i-1\)个子节点与第\(i\)个子节点合并得出的有效信息即为：\(mi_u + l + mi_{v_i}\)
展开说明：我们现在计算的是前\(i-1\)个子节点子树中的一条边与第\(i\)个子节点子树中的一条边连成的边的最小值。
所以我们使前\(i-1\)个子节点的信息最小且使第\(i\)个子节点的信息最小即得整体最小。
最后在更新一下$mi_u = min \lbrace mi_{v_i}+l \rbrace $。

计算\(ans_{max} , mx_{u}\)同理，最后处理棘手的\(ans_{sum},sum_u\)
如上，假设现在已经处理合并好了前\(i-1\)个子节点的信息。
可以知道我们要计算的是前\(i-1\)个子节点的信息总和与\(v_i\)信息总和的合并。
暴力的想，其实就是把前\(i-1\)个子节点的子树中的所有边与\(v_i\)子树中的边一条条匹配求和。
我们有\(sum_u\)表示根据前\(i-1\)个子节点计算出的每个子树内边的长度和，与\(v_i\)的长度和\(sum_{v_i}\)
直接拿出来匹配即可：\(sum_u\times siz_v + l \times siz_u \times siz_v + sum_v \times siz_u\)
展开说明：乘法原理得\(v_i \rightarrow u\)被走了\(siz_u \times siz_v\)次，\(v_1 \dots v_{i-1}\)与\(v_i\)内的边互相匹配。
最后更新\(sum_u \leftarrow sum_u+sum_v+l\times siz_v\)

时间复杂度\(O(qklogk)\approx O(nlogn)\)