概要
次の制約を満たす木の最大の直径を求めよ。
- 一つのノードを選び、これを V とする
- V から最も遠いノードへの距離を D とする
- x ( 1 ≦ x ≦ D ) について、V から距離 x 離れているノードの数が決まっている
解法
木の直径となりうるパスは次のように構築されます。
- ある高さ r の節点を一つ選び v とします
- v から葉方向に伸びる辺を一つ選んで、最も遠い葉までの距離を a とする
- 2.で選んだものとは異なる辺を一つ選んで、最も大きい葉までの距離を b とする( v から葉方向へ伸びる辺が一本しか無い場合は b = 0 )
- 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; } };