题目链接：https://ac.nowcoder.com/acm/contest/2995/E
题意：
树上从u到v简单路径上所有点权中，最大值与最小值的差值为balance(u,v)。
T组(T<=10)，n(1<=n<=5e5)，n个a[i](1<=a[i]<=1e9)表示点权，n-1个u和v，表示u、v两点有边连接，保证构成一棵树
求树的balance%1e9
样例：
答案为179
题解：
最大值与最小值分别计算。
求最大值的方法：从小到大将每个点与相连的点用并查集合并，同时维护每个联通块的size，此时显然可以计算此点作为最大值的路径条数。
计算最小值的方法同理。
思路：
计算最大值先按点权排序
点： 4，5，6，8，9，3，10，7，1，2
点权：2，4，5，5，5，6， 6，8，9，9
先把点④的vis设为1，表示已访问，然后遍历所有与点④相连的已经访问的点，未找到。
再把点⑤的vis设为1，表示已经访问，然后遍历所有与点⑤相连的已经访问的点，找到点④，此时需要做如下处理：
与点④连通的联通块(共有size1个点)的最大点权都为2，与点⑤连通的联通块(共有size2个点)的最大点权都为4，
从左边联通块任取一点，右边联通块里任取一点，两点之间的最大点权都为4，共有size1*size2对点，再乘上⑤的点权4，即为这一部分的max值
然后联合两个块，重新计算size(用并查集维护)，这个块的点权是多少不重要，因为排序是从小到大，乘的都是大的点的点权。
计算完所有max点权之和后，按倒序计算min点权，相减即为答案。
附上代码o(*￣▽￣*)ブ：
#include<bits/stdc++.h> using namespace std; const int maxn=5e5+10; const int mod=1e9+7; int n,fa[maxn],size[maxn],vis[maxn]; pair<int,int> a[maxn]; vector<int> G[maxn]; void init() { for(int i=1;i<=n;i++)fa[i]=i,size[i]=1; memset(vis,0,sizeof vis); } int get(int x) { if(fa[x]==x)return x; return fa[x]=get(fa[x]); } void merge(int a,int b) { a=get(a); b=get(b); if(a!=b) { fa[a]=b; size[b]+=size[a]; } } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d",&n); init(); for(int i=1;i<=n;i++) { scanf("%d",&a[i].first); a[i].second=i; G[i].clear(); } for(int i=1;i<n;i++) { int u,v; scanf("%d%d",&u,&v); G[u].push_back(v); G[v].push_back(u); } sort(a+1,a+1+n); long long ans=0; for(int i=1;i<=n;i++) { int now=a[i].second; vis[now]=1; for(int j:G[now]) { if(vis[j]) { ans=(ans+(1ll*a[i].first*size[now]%mod)*size[get(j)]%mod)%mod; merge(j,now); } } } init(); for(int i=n;i>=1;i--) { int now=a[i].second; vis[now]=1; for(int j:G[now]) { if(vis[j]) { ans=(ans-(1ll*a[i].first*size[now]%mod)*size[get(j)]%mod+mod)%mod; merge(j,now); } } } printf("%lld ",ans); } return 0; }
wa了几发，
return fa[x]=get(fa[x]);写成return get(fa[x]);
G[i]没有写clear()
......