UVA 10938 [Flea circus]

gistfile1.cpp

#include <iostream>
#include <sstream>
#include <bitset>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <numeric>
#include <list>
#define FOR(i,A) for(typeof (A).begin() i = (A).begin() ; i != (A).end() ; i++)
#define mp make_pair
#define debug( x ) cout << #x << " = " << x << endl
#define clr(v,x) memset( v, x , sizeof v )
#define all(x) (x).begin() , (x).end()
#define rall(x) (x).rbegin() , (x).rend()
#define f(i,a,b) for(int i = a ; i < b ; i++)
#define fd(i,a,b) for(int i = a ; i >= b ; i--)
#define PI acos( -1.0 )
#define EPS 1E-9
#define TAM 5010

using namespace std;

typedef pair<int,int> ii ;
typedef long long ll ;
typedef long double ld ;
typedef pair<int,ii> pii ;

vector<int> g[ TAM ] ;
int P[ TAM ][ 20 ] ;
int L[ TAM ] ;
int T[ TAM ] ;
int D[ TAM ] ;
int n ;
int lca ;

void init(){
	f( i , 0 , n ){ L[ i ] = T[ i ] = D[ i ] = 0 ; g[ i ].clear() ; }
	clr( P , 0 ) ;
}

void dfs( int x , int lvl = 1 ){
	L[ x ] = lvl ;
	f( i , 0 , g[ x ].size() ){
		int u = g[ x ][ i ] ;
		if( L[ u ] ) continue ;
		T[ u ] = x ;
		D[ u ] = D[ x ] + 1 ;
		dfs( u , lvl + 1 ) ;
	}
}

void pre(){
	dfs( 0 ) ;
	f( i , 0 , n ) P[ i ][ 0 ] = T[ i ] ;
	for(int j = 1 ; (1<<j) <= n ; j++)
		f( i , 0 , n )
			P[ i ][ j ] = P[ P[ i ][ j - 1 ] ][ j - 1 ] ;
}

int dist( int x , int y ){
	if( x == y ){ lca = x ; return 0 ; }

	if( L[ x ] < L[ y ] ){ int tmp = x ; x = y ; y = tmp ; }

	int log = 0 ;
	for( log = 0 ; (1<<log) <= n ; log++ ) ;
	log-- ;

	int R = 0 ;
	fd( i , log , 0 )
		if( L[ x ] - (1<<i) >= L[ y ] ){
			R += ( D[ x ] - D[ P[ x ][ i ] ] ) ;
			x = P[ x ][ i ] ;
		}

	if( x == y ){ lca = x ; return R ; }

	fd( i , log , 0 )
		if( P[ x ][ i ] != P[ y ][ i ] ){
			R += ( D[ x ] - D[ P[ x ][ i ] ] ) ;
			R += ( D[ y ] - D[ P[ y ][ i ] ] ) ;
			x = P[ x ][ i ] ; y = P[ y ][ i ] ;
		}
	R += ( D[ x ] - D[ P[ x ][ 0 ] ] ) ;
	R += ( D[ y ] - D[ P[ y ][ 0 ] ] ) ;
	lca = P[ x ][ 0 ] ;
	return R ;
}

int kth( int x , int y , int k ){
	int dt = dist( x , y ) ;
	int LCA = lca ;
	int dl = dist( x , LCA ) ;

	int resp , log = 0 ;
	for( log = 0 ; (1<<log) <= n ; log++ ) ;
	log-- ;

	if( dl > k ){
		fd( i , log , 0 )
			if( L[ x ] - (1<<i) >= L[ LCA ] )
				if( k - (1<<i) >= 0 ){
					k -= (1<<i) ;
					x = P[ x ][ i ] ;
				}
		resp = x ;
	}else if( dl < k ){
		k = dt - k ;
		fd( i , log , 0 )
			if( L[ y ] - (1<<i) >= L[ LCA ] )
				if( k - (1<<i) >= 0 ){
					k -= (1<<i) ;
					y = P[ y ][ i ] ;
				}
		resp = y ;
	}else
		resp = LCA ;
	return resp + 1 ;
}

int main(){

	while( scanf("%d" , &n ) == 1 ){
		if( n == 0 ) break ;
		init() ;
		int a , b , q ;
		f( i , 0 , n-1 ){
			scanf("%d%d" , &a , &b ) ;
			a-- ; b-- ;
			g[ a ].push_back( b ) ;
			g[ b ].push_back( a ) ;
		}
		pre() ;
		scanf("%d" , &q ) ;
		f( i , 0 , q ){
			scanf("%d%d" , &a , &b ) ;
			a-- ; b-- ;
			int dd = dist( a , b ) ;
			if( dd & 1 ){
				int r1 = kth( a , b , dd>>1 ) ;
				int r2 = kth( b , a , dd>>1 ) ;
				if( r1 > r2 ){ int tmp = r1 ; r1 = r2 ; r2 = tmp ; }
				printf("The fleas jump forever between %d and %d.\n" , r1 , r2 ) ;
			}else{
				printf("The fleas meet at %d.\n" , kth( a , b , dd>>1 ) ) ;
			}
		}
	}
    return 0 ;
}