2003/Contest/ソウル大会

Problem F : ChonSu

問題概要

木構造のグラフがあり、それは次を満たします。

   ある点は、子を持つとすれば必ず2つである。

このような木があったとして、それの葉の部分には、左のから順に番号が付いているとします。(最大1000まで)

ここで葉を2つ選んだときにその距離(問題中ではChonsu)が定義できます。(枝を辿って葉から葉へ行くときの枝の数)。

ここで、入力としてグラフではなく、

   n番目の葉とn+1番目の葉との距離(n = 1,2,3,.....)

が与えられ(この情報だけで木が復元できます)、

   i番目の葉とj番目の葉との距離

を求める問題です。

難易度

普通。

解法

とりあえず、D(n,n+1) = 2 ならば、それらの葉は、共通の親を持ち、n-1番目やn+2番目の葉から見れば、この親との距離はもとより1小さい。ex D(n-1,n)-1 = D(n-1,parent)

このように距離が2なら共通の親を持つことを利用すれば、木が復元できるでしょう。

議論・その他


ファイルを添付する

[添付ファイル一覧] [全ページの添付ファイル一覧]
アップロード可能最大ファイルサイズは 10,240KB です。

管理者パスワード:

Last-modified: 2009-11-06 (金) 13:26:46 (3243d)