yicongli

CF915F

Oct 18th, 2020
547
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define gc c=getchar()
  6. #define r(x) read(x)
  7. #define ll long long
  8. #define fi first
  9. #define se second
  10.  
  11. template<typename T>
  12. inline void read(T&x){
  13.     x=0;T k=1;char gc;
  14.     while(!isdigit(c)){if(c=='-')k=-1;gc;}
  15.     while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
  16. }
  17.  
  18. const int N=1e6+7;
  19.  
  20. struct Edge{
  21.     int u,v,w;
  22. }E[2][N];
  23.  
  24. inline bool cmp0(const Edge &a,const Edge &b){
  25.     return a.w>b.w;
  26. }
  27.  
  28. inline bool cmp1(const Edge &a,const Edge &b){
  29.     return a.w<b.w;
  30. }
  31.  
  32. ll ans[2];
  33. int a[N],siz[N],fa[N];
  34.  
  35. int find(int x){
  36.     return x==fa[x]?x:fa[x]=find(fa[x]);
  37. }
  38.  
  39. inline void Union(int u,int v){
  40.     siz[fa[u]]+=siz[fa[v]];
  41.     fa[fa[v]]=fa[u];
  42. }
  43.  
  44. int main() {
  45.     int n;r(n);
  46.     for(int i=1;i<=n;++i){
  47.         r(a[i]);
  48.     }
  49.     for(int i=1;i<n;++i){
  50.         int u,v;r(u),r(v);
  51.         E[0][i]={u,v,min(a[u],a[v])};
  52.         E[1][i]={u,v,max(a[u],a[v])};
  53.     }
  54.     sort(E[0]+1,E[0]+n,cmp0);
  55.     sort(E[1]+1,E[1]+n,cmp1);
  56.     for(int k=0;k<2;++k){
  57.         for(int i=1;i<=n;++i){
  58.             fa[i]=i;
  59.             siz[i]=1;
  60.         }
  61.         for(int i=1;i<n;++i){
  62.             int u=E[k][i].u;
  63.             int v=E[k][i].v;
  64.             if(find(u)^find(v)){
  65.                 ans[k]+=(ll)siz[fa[u]]*siz[fa[v]]*E[k][i].w;
  66.                 Union(u,v);
  67.             }
  68.         }
  69.     }
  70.     // printf("%lld\n",ans[0]);
  71.     // printf("%lld\n",ans[1]);
  72.     printf("%lld\n",ans[1]-ans[0]);
  73.     return 0;
  74. }
RAW Paste Data