Submission #239516

---

Source Code Expand

#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <functional>
#include <iterator>
#include <limits>
#include <numeric>
#include <utility>
#include <cmath>

using namespace std; using namespace placeholders;

using LL = long long;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VS = vector<string>;
using SS = stringstream;
using PII = pair<int,int>;
using VPII = vector< pair<int,int> >;
template < typename T = int > using VT = vector<T>;
template < typename T = int > using VVT = VT< VT<T> >;
template < typename T = int > using LIM = numeric_limits<T>;

template < typename T > inline T fromString( const string &s ){ T res; istringstream iss( s ); iss >> res; return res; };
template < typename T > inline string toString( const T &a ){ ostringstream oss; oss << a; return oss.str(); };

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( e, c ) for ( auto &e : c )
#define ALL( c ) (c).begin(), (c).end()
#define AALL( a, t ) (t*)a, (t*)a + sizeof( a ) / sizeof( t )
#define DRANGE( c, p ) (c).begin(), (c).begin() + p, (c).end()

#define PB( n ) push_back( n )
#define MP( a, b ) make_pair( ( a ), ( b ) )
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

#define fst first
#define snd second

#define DUMP( x ) cerr << #x << " = " << ( x ) << endl

class LowestCommonAncestor
{
private:
	const int N;
	std::vector< std::vector<int> > G;

	bool constructed = false;
	std::vector<int> depth_;
	std::vector< std::vector<int> > parent_;

public:
	LowestCommonAncestor( const int n ) : N( n ), G( N ), depth_( N ), parent_( N, std::vector<int>( 31, -1 ) )
	{
		return;
	}

	LowestCommonAncestor( const std::vector< std::vector<int> > &g ) : N( g.size() ), G( g ), depth_( N ), parent_( N, std::vector<int>( 31, -1 ) )
	{
		return;
	}

	void connect( const int u, const int v )
	{
		G[u].push_back( v );
		G[v].push_back( u );
		constructed = false;

		return;
	}

	int depth( const int u ) const
	{
		return depth_[u];
	}

	int solve( int u, int v )
	{
		if ( !constructed )
		{
			dfs( 0, -1, 0 );
			doubling();
			constructed = true;
		}

		if ( depth_[u] < depth_[v] )
		{
			swap( u, v );
		}

		{ // align depths
			int diff = depth_[u] - depth_[v];
			for ( int i = 30; 0 <= i; --i )
			{
				if ( diff & 1 << i )
				{
					u = parent_[u][i];
				}
			}
		}

		if ( u == v )
		{
			return u;
		}

		for ( int i = 30; 0 <= i; --i )
		{
			if ( parent_[u][i] != parent_[v][i] )
			{
				u = parent_[u][i];
				v = parent_[v][i];
			}
		}

		return parent_[u][0];
	}

private:
	void dfs( const int u, const int prev, const int d )
	{
		depth_[u] = d;
		parent_[u][0] = prev;

		for ( const int v : G[u] )
		{
			if ( v == prev )
			{
				continue;
			}

			dfs( v, u, d + 1 );
		}

		return;
	}

	void doubling()
	{
		for ( int i = 0; i < 30; ++i )
		{
			for ( int u = 0; u < N; ++u )
			{
				if ( parent_[u][i] != -1 )
				{
					parent_[u][ i + 1 ] = parent_[ parent_[u][i] ][i];
				}
			}
		}
		return;
	}
};



int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n;
	cin >> n;

	LowestCommonAncestor lca( n );
	REP( i, 0, n - 1 )
	{
		int a, b;
		cin >> a >> b;
		lca.connect( a - 1, b - 1 );
	}

	int q;
	cin >> q;

	REP( iteration, 0, q )
	{
		int a, b;
		cin >> a >> b;
		a--, b--;

		const int anc = lca.solve( a, b );

		cout << lca.depth( a ) + lca.depth( b ) - 2 * lca.depth( anc ) + 1 << endl;
	}

	return 0;
}

Submission Info

Judge Result