【AtCoder】M-SOLUTIONSプロコンオープン D - Maximum Sum of Minimum

N頂点の木とN個の正整数が与えられ，各頂点に1つずつ正整数を任意の順で書き込んでいく。そして各辺の両端に書かれいている正整数 a,b のうち小さいほう (min(a,b)) をスコアに加算していく。

このとき取り得るスコアの最大値とその場合の書き込み方を出力せよ。

次数の少ない頂点から順に小さい正整数を書き込めば，小さい正整数が評価される回数が少なくなるのではと考えた。

しかしこの方針ではWAとなった......。

どうやら下図のような場合がダメとなるよう（「5と6, 6と7」と評価できるところを「5と6, 5と7」と評価している）。

最大の正整数はスコアに加算できない。二番目以降に大きい正整数は，自分より大きいものと繋がればスコアに加算される。

大きい正整数から書き込んでいくと，二番目に大きい正整数は1回しかスコアに貢献できず，また同様に三番目以降の正整数も1回しかスコアに貢献できなくなる。これが最大のスコアを取る方法のようだ。

DFSで大きい正整数から書き込んでいけばよい。

なかなか解法が思い浮かばなかったんですが，他の方のコード見ると確かにと納得できました。もっとセンスよく正解のイメージをできるようになりたいですね。