Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define sc( x ) scanf( "%d" , &x )
- #define REP( i , n ) for( int i = 0 ; i < n ; ++i )
- #define clr( t , val ) memset( t , val , sizeof( t ) )
- #define pb push_back
- #define all( v ) v.begin() , v.end()
- #define SZ( v ) ((int)v.size())
- #define mp make_pair
- #define fi first
- #define se second
- #define N 200000
- #define INF (INT_MAX)
- #define test cout << "*************test**************" << endl;
- typedef vector< int > vi;
- typedef pair< int , int > pii;
- typedef vector< pii > vpii;
- typedef long long ll;
- typedef vector< ll > vll;
- vi G[ 2 * N + 5 ];
- int in[ 2 * N + 5 ] , out[ 2 * N + 5 ] , vis[ 2 * N + 5 ] , DP[ 2 * N + 5 ];
- int timer ;
- int X[ 2 * N + 5 ];
- pii A[ 2 * N + 5 ] ;
- int outdeg[ 2 * N + 5 ];
- void dfs( int u , int p , int n ){
- vis[ u ] = 1;
- in[ u ] = timer ;
- A[ timer ] = mp( X[ u ] , u );
- timer ++;
- DP[ u ] = 1;
- REP( i , SZ( G[ u ] ) ){
- int v = G[ u ][ i ];
- if( !vis[ v ] && v != p ) {
- outdeg[ u ] ++;
- dfs( v , u , n );
- DP[ u ] += DP[ v ];
- }
- }
- out[ u ] = timer ;
- }
- #define v1 ((node<<1)+1)
- #define v2 (v1+1)
- #define med ((a+b)>>1)
- #define LEFT v1 , a , med
- #define RIGHT v2 , med + 1 , b
- vpii T[ 4 * N + 5 ];
- vll T2[ 4 * N + 5 ];
- vll TR2[ 4 * N + 5 ];
- vpii pull( vpii a , vpii b ){
- vpii c( SZ( a ) + SZ( b ) );
- merge( all( a ) , all( b ) , c.begin() );
- return c;
- }
- vll getAC( vpii &v ){
- vll AC( SZ( v ) + 1 );
- REP( i , SZ( v ) ) AC[ i + 1 ] = AC[ i ] + v[ i ].fi;
- return AC;
- }
- vll getAC2( vpii &v ){
- vll AC( SZ( v ) + 1 );
- for( int i = SZ( v ) - 1 ; i >= 0 ; --i ) AC[ i ] = AC[ i + 1 ] + v[ i ].fi;
- return AC;
- }
- void build_tree( int node , int a , int b ){
- if( a == b ){
- T[ node ] = vpii( 1 , A[ a ] );
- T2[ node ] = getAC( T[ node ] );
- TR2[ node ] = getAC2( T[ node ] );
- return;
- }
- build_tree( LEFT ) , build_tree( RIGHT );
- T[ node ] = pull( T[ v1 ] , T[ v2 ] );
- T2[ node ] = getAC( T[ node ] );
- TR2[ node ] = getAC2( T[ node ] );
- }
- vi ind;
- void query( int node , int a , int b , int lo , int hi ){
- if( lo > b || a > hi ) return;
- if( a >= lo && hi >= b ){
- ind.pb( node );
- return;
- }
- query( LEFT , lo , hi );
- query( RIGHT , lo , hi );
- }
- ll f( int pos , int &cnt ){
- ll slo = 0 , shi = 0;
- cnt = 0;
- REP( u , SZ( ind ) ){
- int y = upper_bound( all( T[ ind[ u ] ] ) , A[ pos ] ) - T[ ind[ u ] ].begin();
- shi += TR2[ ind[ u ] ][ y ];
- int x = lower_bound( all( T[ ind[ u ] ] ) , A[ pos ] ) - T[ ind[ u ] ].begin();
- cnt += x;
- x --;
- slo += T2[ ind[ u ] ][ x + 1 ];
- }
- return abs( shi - slo );
- }
- int g( int pos ){
- int cnt = 0 ;
- REP( u , SZ( ind ) )
- cnt += lower_bound( all( T[ ind[ u ] ] ) , A[ pos ] ) - T[ ind[ u ] ].begin();
- return cnt;
- }
- int get( int u , int n ){
- if( outdeg[ u ] == 0 ) return u;
- int x = in[ u ] , y = out[ u ];
- ind.clear();
- query( 0 , 0 , timer - 1 , x , y );
- int lo = 0 , hi = timer - 1 , s , t;
- while( hi - lo > 4 ){
- int med1 = (lo*2 + hi)/3 , med2 = (lo + hi*2)/3;
- if( f( med1 , s ) < f( med2 , s ) )
- hi = med2;
- else lo = med1;
- }
- int pos = lo;
- for( int i = max( 0 , lo - 4 ) ; i <= min( timer - 1 , hi + 4 ) ; ++i )
- if( f( i , s ) < f( pos , s ) ) pos = i;
- f( pos , t );
- //cout << "val = " << f( pos , t ) << endl;
- //cout << t << endl;
- lo = 0 , hi = timer - 1;
- if( g( lo ) >= t ) return A[ lo ].se;
- while( hi - lo > 1 ){
- int mid = (lo + hi)/2;
- if( g( mid ) >= t ) hi = mid;
- else lo = mid;
- }
- return A[ hi ].se;
- }
- int main(){
- int cases , n , p , lo , hi;
- while( sc( n ) == 1 ){
- REP( i , N ) G[ i ].clear();
- clr( outdeg , 0 );
- REP( i , n ) sc( X[ i ] );
- REP( i , n - 1 ){
- int u , v;
- sc( u ) , sc( v );
- u -- , v --;
- G[ u ].pb( v );
- G[ v ].pb( u );
- }
- timer = 0;
- clr( vis , 0 );
- dfs( 0 , -1 , n );
- build_tree( 0 , 0 , timer - 1 );
- sort( A , A + timer );
- int Q;
- sc( Q );
- vi freq( n );
- REP( it , Q ){
- int u;
- sc( u );
- u --;
- int v = get( u , n );
- freq[ v ] ++;
- //cout << u + 1 << " " << v + 1 << endl;
- }
- int maxi = -1 , ind = -1;
- REP( i , n ) if( freq[ i ] > maxi ) maxi = freq[ i ] , ind = i;
- printf( "%d %d\n" , ind + 1 , maxi );
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement