TopCoder SRM 591, Division 1, Level 1 : TheTree

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12746&rd=15703

概要

次の制約を満たす木の最大の直径を求めよ。

1. 一つのノードを選び、これを V とする
2. V から最も遠いノードへの距離を D とする
3. x ( 1 ≦ x ≦ D ) について、V から距離 x 離れているノードの数が決まっている

解法

木の直径となりうるパスは次のように構築されます。

1. ある高さ r の節点を一つ選び v とします
2. v から葉方向に伸びる辺を一つ選んで、最も遠い葉までの距離を a とする
3. 2.で選んだものとは異なる辺を一つ選んで、最も大きい葉までの距離を b とする（ v から葉方向へ伸びる辺が一本しか無い場合は b = 0 )
4. a + b が直径の候補

1 ≦ cnt[ i ] の制約から、a の値は v から最も遠い葉までの距離になります。
残った辺から別のパスを伸ばしますが、2 ≦ cnt[ i ] ならば下方向に伸ばせるので、1 が出てくるまで伸ばし続ければよいです。

v を決めたときの最大直径の求め方が分かったので、r を全部試せば解けます。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

class TheTree
{
public:
	int maximumDiameter( vector <int> cnt )
	{
		int H = cnt.size();

		int res = 0;
		REP( r, 0, H )
		{
			int tmp = H - r;;
			for ( int i = r; i < H && 2 <= cnt[i]; i++ )
			{
				tmp++;
			}
			res = max( res, tmp );
		}
		return res;
	}
};