fork download
copy 
  1. //niceduck
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. typedef long long ll;
  5. #define FILE "000"
  6. #define fastio ios_base::sync_with_stdio(0);cin.tie(0);
  7. #define foru(i,a,b) for(int i=(int)(a); i<=(int)(b); ++i)
  8. #define ford(i,a,b) for(int i=(int)(a); i>=(int)(b); --i)
  9. #define fi first
  10. #define se second
  11. #define el "\n"
  12. #define pb push_back
  13. #define pii pair<int,int>
  14.  
  15. const int MAX=3e5+5,MOD=1e9+7;
  16. int n,in[MAX];
  17. ll cntLeaf,leaf[MAX],a[MAX],pass[MAX];
  18. vector<int> adj[MAX];
  19.  
  20. void dfs(int u, int p)
  21. {
  22.     if(in[u]==1)
  23.     {
  24.         leaf[u]=1;
  25.         return;
  26.     }
  27.     ll tmp=0;
  28.     for(int v:adj[u])
  29.     {
  30.         if(v==p) continue;
  31.         dfs(v,u);
  32.         leaf[u]+=leaf[v];
  33.         tmp+=(leaf[v]*(leaf[v]-1)/2);
  34.     }
  35. //    cout<<u<<' '<<leaf[u]<<' '<<in[u]<<el;;
  36.     pass[u]=(leaf[u]-1)*leaf[u]/2;
  37.     pass[u]-=tmp;
  38.     pass[u]+=leaf[u]*(cntLeaf-leaf[u]);
  39. }
  40.  
  41. void reset()
  42. {
  43.     cntLeaf=0;
  44.     foru(i,1,n)
  45.     {
  46.         leaf[i]=pass[i]=in[i]=0;
  47.         adj[i].clear();
  48.     }
  49. }
  50.  
  51. int main()
  52. {
  53.     fastio
  54.     if(fopen(FILE ".inp","r"))
  55.     {
  56.         freopen(FILE ".inp","r",stdin); freopen(FILE ".out", "w",stdout);
  57.     }
  58.     int t; cin>>t;
  59.     while(t--)
  60.     {
  61.         cin>>n;
  62.         reset();
  63.         foru(i,1,n) cin>>a[i];
  64.         foru(i,2,n)
  65.         {
  66.             int u,v; cin>>u>>v;
  67.             adj[u].pb(v);
  68.             adj[v].pb(u);
  69.             in[u]++; in[v]++;
  70.         }
  71.         int root=-1;
  72.         foru(i,1,n)
  73.         {
  74.             if(in[i]>1)
  75.             {
  76.                 root=i;
  77.                 break;
  78.             }
  79.         }
  80.         foru(i,1,n) if(in[i]==1) ++cntLeaf;
  81.         dfs(root,0);
  82.         vector<ll> v;
  83.         v.clear();
  84.         foru(i,1,n)
  85.         {
  86.             if(in[i]>1) v.pb(pass[i]);
  87.             else v.pb(cntLeaf-1);
  88.         }
  89.         sort(a+1,a+n+1);
  90.         sort(v.begin(),v.end());
  91.         ll ans=0;
  92.         foru(i,1,n) ans=(ans+(((v[i-1]%MOD)*a[i])%MOD))%MOD;
  93.         cout<<ans<<el;
  94.     }
  95.     return 0;
  96. }
  97.  
Success #stdin #stdout 0.01s 11412KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Swfbyd
language:
C++14 (gcc 8.3)
created:
15 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!