AtCoder Grand Contest 005: C. Tree Restoring

http://agc005.contest.atcoder.jp/tasks/agc005_c

解法

まず直径のパスを先に作ろう。直径は a[i] の最大値。

たとえば直径が 5 だったら先に次のパスを構築する。

この段階で作れないなら Impossible。

もし a[i]≦3 が余ってたら、どうやっても構成不可能。一方で、a[i]>3は大量に余っていても問題にならない。

例えば 4 が余ってたら、次のように繋いでおけばいい。

もう一個 4 が余ってたら、次のように繋いでおけばいい。

というように、a[i]>3はどうにでもなる。

CFのBあたりに構築ゲーとして出てきそうな問題。