树剖维护一下即可。
注意多组数据要彻底清空！
原式拆为每个区间的最大值减去最小值，分开算两个答案，如最大值
考虑每个元素可能在哪些区间成为最大值，也就是在左边第一个比它大的和右边第一个比它大的之间，贡献就是区间个数*该元素本身
这个区间可以通过RMQ+二分求出，总复杂度O(nlogn)
多组数据清空！！
来自wxl学长~
统计每条边的贡献（即经过了几次），发现在一个图上瞎走有C(n,2)=n*(n-1)/2种方案，其中在此边子树中走的不算，非子树的不算，剩下的就是跨越这条边的数量.
有哪些[L,R]是完全在子树中的呢？不妨考虑把子树中的点放到一个桶里，构成一个01序列，显然，一个区间[L,R]若全是1，则一定是一个在子树中的走法.
现在的问题是，如何求一个01序列中,[L,R]均为1的个数？不难发现这个就是每段中选两个点的方案，也就是ΣC(len,2).
因此我们要维护一个序列中的连续的1，怎么做呢？
可以用一个map维护L，一个map维护R，这样就可以logn地插入、查询了.
至于合并子树，可以用dsu on tree的方法，做到O(nlognlogn).
当然，我们发现其实map有些大材小用，一个哈希表完全就可以做到这个功能，这样就是O(nlogn)的.