AtCoder Grand Contest 005 C 「Tree Restoring」

問題文

C - Tree Restoring

 

N=2のとき、作れる木は二頂点を直接つないだグラフだけ。N>2のとき、最も遠い頂点までの距離が1の頂点があるとすると、他の全ての頂点はその頂点に直接つながっているのでスターになる。よって、N=2のときとa[i]=1となるiがあるときは簡単に判定ができる。以下ではN>2かつa[i]≠1と仮定する。

a[i]の最大値をMとすると、Mは木の直径になる。絵を描いてみると(M=4のときの図を以下に示す)、次のことがわかるので、その通りに判定してやればいい。

(i) Mが偶数のとき

・a[i]=M,M-1,...,M/2+1となるiは2つ以上ないといけない

・a[i]=1,2,...,M/2-1となるiがあってはいけない

・a[i]=M/2となるiはちょうど1つないといけない

(ii) Mが奇数のとき

・a[i]=M,M-1,...,(M+1)/2+1となるiは2つ以上ないといけない

・a[i]=1,2,...,(M+1)/2-1となるiがあってはいけない

・a[i]=(M+1)/2となるiはちょうど2つないといけない

 

 f:id:Div9851P:20190106184916p:plain