Advertisement
BoxerTC

Untitled

Mar 24th, 2015
236
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.17 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define sc( x ) scanf( "%d" , &x )
  5. #define REP( i , n ) for( int i = 0 ; i < n ; ++i )
  6. #define clr( t , val ) memset( t , val , sizeof( t ) )
  7.  
  8. #define pb push_back
  9. #define all( v ) v.begin() , v.end()
  10. #define SZ( v ) ((int)v.size())
  11.  
  12. #define mp make_pair
  13. #define fi first
  14. #define se second
  15.  
  16. #define N 200000
  17. #define INF (INT_MAX)
  18.  
  19. #define test cout << "*************test**************" << endl;
  20.  
  21. typedef vector< int > vi;
  22. typedef pair< int , int > pii;
  23. typedef vector< pii > vpii;
  24. typedef long long ll;
  25. typedef vector< ll > vll;
  26.  
  27. vi G[ 2 * N + 5 ];
  28. int in[ 2 * N + 5 ] , out[ 2 * N + 5 ] , vis[ 2 * N + 5 ] , DP[ 2 * N + 5 ];
  29. int timer ;
  30.  
  31. int X[ 2 * N + 5 ];
  32. pii A[ 2 * N + 5 ] ;
  33. int outdeg[ 2 * N + 5 ];
  34. void dfs( int u , int p , int n ){
  35.     vis[ u ] = 1;
  36.     in[ u ] = timer ;
  37.     A[ timer ] = mp( X[ u ] , u );
  38.     timer ++;
  39.     DP[ u ] = 1;
  40.     REP( i , SZ( G[ u ] ) ){
  41.         int v = G[ u ][ i ];
  42.         if( !vis[ v ] && v != p ) {
  43.             outdeg[ u ] ++;
  44.             dfs( v , u , n );
  45.             DP[ u ] += DP[ v ];
  46.         }
  47.     }
  48.     out[ u ] = timer ;
  49. }
  50.  
  51. #define v1 ((node<<1)+1)
  52. #define v2 (v1+1)
  53. #define med ((a+b)>>1)
  54. #define LEFT v1 , a , med
  55. #define RIGHT v2 , med + 1 , b
  56.  
  57. vpii T[ 4 * N + 5 ];
  58. vll T2[ 4 * N + 5 ];
  59. vll TR2[ 4 * N + 5 ];
  60. vpii pull( vpii a , vpii b ){
  61.     vpii c( SZ( a ) + SZ( b ) );
  62.     merge( all( a ) , all( b ) , c.begin() );
  63.     return c;
  64. }
  65. vll getAC( vpii &v ){
  66.     vll AC( SZ( v ) + 1 );
  67.     REP( i , SZ( v ) ) AC[ i + 1 ] = AC[ i ] + v[ i ].fi;
  68.     return AC;
  69. }
  70. vll getAC2( vpii &v ){
  71.     vll AC( SZ( v ) + 1 );
  72.     for( int i = SZ( v ) - 1 ; i >= 0 ; --i ) AC[ i ] = AC[ i + 1 ] + v[ i ].fi;
  73.     return AC;
  74. }
  75. void build_tree( int node , int a , int b ){
  76.     if( a == b ){
  77.         T[ node ] = vpii( 1 , A[ a ] );
  78.         T2[ node ] = getAC( T[ node ] );
  79.         TR2[ node ] = getAC2( T[ node ] );
  80.         return;
  81.     }
  82.     build_tree( LEFT ) , build_tree( RIGHT );
  83.     T[ node ] = pull( T[ v1 ] , T[ v2 ] );
  84.     T2[ node ] = getAC( T[ node ] );
  85.     TR2[ node ] = getAC2( T[ node ] );
  86. }
  87. vi ind;
  88. void query( int node , int a , int b , int lo , int hi ){
  89.     if( lo > b || a > hi ) return;
  90.     if( a >= lo && hi >= b ){
  91.         ind.pb( node );
  92.         return;
  93.     }
  94.     query( LEFT , lo , hi );
  95.     query( RIGHT , lo , hi );
  96. }
  97.  
  98. ll f( int pos , int &cnt ){
  99.     ll slo = 0 , shi = 0;
  100.     cnt = 0;
  101.     REP( u , SZ( ind ) ){
  102.         int y = upper_bound( all( T[ ind[ u ] ] ) , A[ pos ] ) - T[ ind[ u ] ].begin();
  103.         shi += TR2[ ind[ u ] ][ y ];
  104.         int x = lower_bound( all( T[ ind[ u ] ] ) , A[ pos ] ) - T[ ind[ u ] ].begin();
  105.         cnt += x;
  106.         x --;
  107.         slo += T2[ ind[ u ] ][ x + 1 ];
  108.     }
  109.     return abs( shi - slo );
  110. }
  111. int g( int pos ){
  112.     int cnt = 0 ;
  113.     REP( u , SZ( ind ) )
  114.         cnt += lower_bound( all( T[ ind[ u ] ] ) , A[ pos ] ) - T[ ind[ u ] ].begin();    
  115.     return cnt;
  116. }
  117. int get( int u  , int n ){
  118.     if( outdeg[ u ] == 0 ) return u;
  119.     int x = in[ u ] , y = out[ u ];
  120.     ind.clear();
  121.     query( 0 , 0 , timer - 1 , x , y );
  122.     int lo = 0 , hi = timer - 1 , s , t;
  123.     while( hi - lo > 4 ){
  124.         int med1 = (lo*2 + hi)/3 , med2 = (lo + hi*2)/3;
  125.         if( f( med1 , s ) < f( med2 , s ) )
  126.             hi = med2;
  127.         else lo = med1;
  128.     }
  129.     int pos = lo;
  130.     for( int i = max( 0 , lo - 4 ) ; i <= min( timer - 1 , hi + 4 ) ; ++i )
  131.         if( f( i , s ) < f( pos , s ) ) pos = i;
  132.     f( pos , t );
  133.     //cout << "val = " << f( pos , t ) << endl;
  134.     //cout << t << endl;
  135.     lo = 0 , hi = timer - 1;
  136.     if( g( lo ) >= t ) return A[ lo ].se;
  137.     while( hi - lo > 1 ){
  138.         int mid = (lo + hi)/2;
  139.         if( g( mid ) >= t ) hi = mid;
  140.         else lo = mid;
  141.     }
  142.     return A[ hi ].se;
  143. }
  144.  
  145. int main(){
  146.     int cases , n , p , lo , hi;
  147.     while( sc( n ) == 1 ){
  148.         REP( i , N ) G[ i ].clear();
  149.         clr( outdeg , 0 );
  150.         REP( i , n ) sc( X[ i ] );
  151.  
  152.         REP( i , n - 1 ){
  153.             int u , v;
  154.             sc( u ) , sc( v );
  155.             u -- , v --;
  156.             G[ u ].pb( v );
  157.             G[ v ].pb( u );
  158.         }
  159.  
  160.         timer = 0;
  161.         clr( vis , 0 );
  162.         dfs( 0 , -1 , n );
  163.         build_tree( 0 , 0 , timer - 1 );
  164.         sort( A , A + timer );
  165.        
  166.         int Q;
  167.         sc( Q );
  168.         vi freq( n );
  169.         REP( it , Q ){
  170.             int u;
  171.             sc( u );
  172.             u --;
  173.             int v = get( u , n );
  174.             freq[ v ] ++;
  175.             //cout << u + 1 << " " << v + 1 << endl;
  176.         }
  177.         int maxi = -1 , ind = -1;
  178.         REP( i , n ) if( freq[ i ] > maxi ) maxi = freq[ i ] , ind = i;
  179.         printf( "%d %d\n" , ind + 1 , maxi );
  180.     }
  181. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement