Problem F : ChonSu †問題概要 †木構造のグラフがあり、それは次を満たします。 ある点は、子を持つとすれば必ず２つである。 このような木があったとして、それの葉の部分には、左のから順に番号が付いているとします。（最大1000まで） ここで葉を２つ選んだときにその距離(問題中ではChonsu)が定義できます。（枝を辿って葉から葉へ行くときの枝の数）。 ここで、入力としてグラフではなく、 n番目の葉とn+1番目の葉との距離(n = 1,2,3,.....) が与えられ（この情報だけで木が復元できます）、 i番目の葉とj番目の葉との距離 を求める問題です。 難易度 †普通。 解法 †とりあえず、D(n,n+1) = 2 ならば、それらの葉は、共通の親を持ち、n-1番目やn+2番目の葉から見れば、この親との距離はもとより１小さい。ex D(n-1,n)-1 = D(n-1,parent) このように距離が２なら共通の親を持つことを利用すれば、木が復元できるでしょう。 議論・その他 †ファイルを添付する † |
