定义 \(f(u, v)\) 表示 \(u\) 到 \(v\) 路径上的最大与最小点权之差，求：
\[\sum_{i=1}^{n}\sum_{j=i}^{n}f(i,j)
\]
定义 \(\max(u,v)\)，\(\min(u,v)\) 为路径最大最小点权，所求即：
\[\sum_{i=1}^{n}\sum_{j=i}^{n}\max(i,j)-\sum_{i=1}^{n}\sum_{j=i}^{n}\min(i,j)
\]
考虑 \(a_i\) 对左边的和式的贡献，当且仅当其为某条路径 \(u\rightarrow v\) 上的最大值时，会产生贡献。
设边权 \(w_i\) 为端点点权较大值。
那么对 \(w_i\) 升序排序，逐次连边，那么我连接 \(u_i\) 和 \(v_i\) 之前，图中必然只包含边权更小的边，此时边 \(i\) 的加入必然会造成 \(w_i\times siz_{u_i}\times siz_{v_i}\) 的贡献。因为有这么多条边穿过了 \(i\)，而 \(w_i\) 就是其上的最大值。
这实际上已经去重了，边权相同的边先后加入，这时路径上的多个最大值只会在后加入的最大值上算一个。