AtCoder Regular Contest #022, C : ロミオとジュリエット

問題文

http://arc022.contest.atcoder.jp/tasks/arc022_3

問題概要

　N 頂点からなる木が与えられる。この木の最遠頂点対を一つ出力せよ。

解法

　最遠頂点対を結ぶパス = 木の直径 なので、木の直径を求める問題と言い換えられます。木の直径を求めるには、まずある適当な頂点から DFS をして最遠点を求め v とし、次に v からの最遠点を求めて u とすれば、( v, u ) を結ぶ単純道は木の直径となっています。

コード

using VI = vector<int>;
using VVI = vector<VI>;
template < typename T = int > using LIM = numeric_limits<T>;

#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 PB( n ) push_back( n )

constexpr int INF = LIM<>::max() / 2;

struct Solver
{
	const int N;
	const VVI G;

	VI distance;

	Solver( const VVI &g ) : N( g.size() ), G( g ), distance( N ) {};

	VI solve( const int s )
	{
		dfs( s, 0, -1 );
		return distance;
	}

	void dfs( const int v, const int d, const int p )
	{
		distance[v] = d;

		FOR( u, G[v] )
		{
			if ( u == p )
			{
				continue;
			}

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

		return;
	}
};

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

	int n;
	cin >> n;

	VVI G( n );

	REP( i, 0, n - 1 )
	{
		int a, b;
		cin >> a >> b;
		a--, b--;

		G[a].PB( b );
		G[b].PB( a );
	}

	Solver solver( G );

	VI dists1 = solver.solve( 0 );
	const int v = max_element( ALL( dists1 ) ) - dists1.begin();

	VI dists2 = solver.solve( v );
	const int u = max_element( ALL( dists2 ) ) - dists2.begin();

	cout << v + 1 << ' ' << u + 1 << endl;

	return 0;
}