fork download
copy 
  1. #include "bits/stdc++.h"
  2. using namespace std ;
  3.  
  4. #define timesaver ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  5.  
  6. typedef long long ll ;
  7. typedef long double ldb ;
  8.  
  9. #define mp make_pair
  10. #define pb push_back
  11. #define F first
  12. #define S second
  13. #define nl '\n'
  14.  
  15. #define all( x ) x.begin(),x.end() 
  16. #define sz( x ) ( int )( x ).size( )
  17. #define mem( a, val ) memset(a, val, sizeof( a ) )
  18. #define deci( x ) cout<<fixed<<setprecision( x );
  19. #define bitcount( x ) __builtin_popcountll( x )
  20.  
  21. const int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
  22. const int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
  23.  
  24. const int MAX = 2*1000*100 + 10 ;
  25. const ll INF = 1e18 ;
  26. const int MOD = 1e9 + 7 ;
  27.  
  28. struct Query{
  29.   ll l, r, k, idx ;
  30.   bool operator <( Query &b ){
  31.     return k < b.k ;
  32.   }
  33. }qr[ MAX ];
  34.  
  35. struct Array{
  36.   ll val, idx ;
  37.   bool operator <( Array &b ){
  38.     return val < b.val ;
  39.   }
  40. }ar[ MAX ];
  41.  
  42. ll BIT[ MAX ], ans[ MAX ] ;
  43.  
  44. void update( ll pos, ll val ){
  45.   while( pos and pos < MAX ){
  46.     BIT[ pos ] += val ;
  47.     pos += ( pos&-pos );
  48.   }
  49. }
  50.  
  51. ll get( ll pos ){
  52.   ll ans(0);
  53.   while( pos ){
  54.     ans += BIT[ pos ] ;
  55.     pos -= ( pos&-pos ) ;
  56.   }
  57.   return ans ;
  58. }
  59.  
  60. ll timer ;
  61. vector< ll > v[ MAX ], sub( MAX, 0 ), ind( MAX, 0 ) ;
  62.  
  63. void dfs( ll x, ll p ){
  64.   ind[ x ] = ++timer ;
  65.   sub[ x ] = 1 ;
  66.   for( ll i : v[ x ] )
  67.     if( i != p ){
  68.       dfs( i, x ) ;
  69.       sub[ x ] += sub[ i ] ;
  70.     }
  71. }
  72.  
  73. int main( ){
  74.   timesaver ;
  75.   ll n ;
  76.   cin >> n ;
  77.   for( ll i = 1 ; i < n ; i++ ){
  78.     ll x, y ;
  79.     cin >> x >> y ;
  80.     v[ x ].pb( y ) ;
  81.     v[ y ].pb( x ) ;
  82.   }
  83.   timer = 0 ;
  84.   dfs( 1, 1 );
  85.   for( ll i = 1 ; i <= n ; i++ ){
  86.     cin >> ar[ i ].val ;
  87.     ar[ i ].idx = ind[ i ] ;
  88.   }
  89.   for( ll i = 1 ; i <= n ; i++ ){
  90.     qr[ i ].l = ind[ i ] ;
  91.     qr[ i ].r = ind[ i ] + sub[ i ] - 1 ;
  92.     qr[ i ].k = ar[ i ].val ;
  93.     qr[ i ].idx = i ;
  94.   }
  95.   sort( ar + 1, ar + n + 1 ) ;
  96.   sort( qr + 1, qr + n + 1 ) ;
  97.   ll cur( 1 ) ;
  98.   for( ll i = 1 ; i <= n ; i++ ){
  99.     while( ar[ cur ].val < qr[ i ].k and cur <= n ){
  100.       update( ar[ cur ].idx, ar[ cur ].val ) ;
  101.       cur++ ;
  102.     }
  103.     ans[ qr[ i ].idx ] = get( qr[ i ].r ) - get( qr[ i ].l - 1 ) ;
  104.   }
  105.   ll tot( 0 ) ;
  106.   for( ll i = 1 ; i <= n ; i++ )
  107.     tot += ans[ i ] ;
  108.   cout << tot << nl ;
  109. }
Success #stdin #stdout 0s 11004KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/KFJUZJ
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!