AtCoder Beginner Contest 026 C - 高橋君の給料

C - 高橋君の給料

時間制限 : 2sec / メモリ制限 : 256MB

問題文

高橋君は、社員が N 人いる会社の社長です。高橋君の会社では、以下のように給料が決まっています。

高橋君を含む社員の全員が、 1 から N までの社員番号を持っている。高橋君の社員番号はもちろん 1 である。 高橋君以外の社員には、必ず自分より社員番号が小さい上司がただ一人存在する。自分が上司になっている社員のことを、直属の部下と呼ぶ。 直属の部下がいない社員の給料は 1 であり、直属の部下がいる社員の給料は 、max(その社員の直属の部下の給料)+min(その社員の直属の部下の給料)+1 である。直属の部下が一人しかいない場合は、その部下の給料の 2 倍 + 1 が、その社員の給料となる。 この時、高橋君の給料を求めなさい。

note

社員をノード、上司と部下の関係を辺にする木がつくれる。木の末端が給料１となり、ある親ノードからの小ノードを全て調べると、その親ノードの給料が決まるので、深さ優先で木の末端から給料を決めていく。