はじめに
突然書きたくなったので書きます。例によって正当性とかそういうのは放置です。
問題リンク
提出コード
考察プロセス
まず高橋君が通る経路は、選ばれた頂点と根までのパスで通る頂点によって構成される部分木をDFSで通る経路になります。こうすることで、必要な辺を2回だけ通ることですべての頂点を回ることができます。（これ自体が典型？）すなわち、通る必要がある辺の合計長×2が答えになります。従い、最後に求める答えを2倍する形で、いったん合計長だけを考えましょう。（以降の画像による例示は合計長のみですので注意してください。）
次に青木君が選ぶべき頂点は葉になります。もし、葉ではないノードを選んだ場合、その子ノードを選ぶ方が親子を結ぶ辺の長さ分スコアを伸ばせるからです。
また、Kを増やす過程で過去選んでいる頂点に基づく経路上にある頂点はスコアを伸ばすことはできません。そして、すべての葉を選んだあとは、選ぶ頂点の数を増やしてもスコアを上げることができなくなります。
続いて、各小問題でどの葉を選ぶべきか考えていきましょう。
まずK=1の場合を考えましょう。この場合は簡単で、根から葉までの辺の合計長が最も長いものを選べばスコアを最大化することができます。
続いて、そこからK=2,3,...に増やすことを考えます。過去選んだ頂点とその点を往復する経路がすでに存在していますから、2つ目に選ぶ頂点次第では、途中の経路からある種寄り道をするような経路を高橋君は選択することになります。
従い、根→葉の合計長ではなく、すでにあらわている経路で使われてしまっている頂点で一番近い頂点までの合計長が各葉によって伸ばせるスコアになります。
また、ある葉を選ぶ前に選ぶ葉を増やしても、スコアの伸び量が減ることがあっても増えることはありません。よって、ある頂点を選ぶことを後回しにする必要はないので、頂点を増やすときに都度最もスコアの伸び量が多いものを選べばよいです。（ここはロジック的に弱い気がする）
さて、K≧2の場合、どうやって最適な葉を選ぶのか…ですが、その前に選ぶのが頂点なのに対して、スコアは辺で計算されて扱いにくいので、スコアは辺の子側の頂点にあるものとして読み替えます。（どこかで見たけど典型な気がする）
結果としてスコアの伸びとしては、辺の合計長ではなく通過する頂点スコアの合計に置き換わります。なお、根のスコアは0とします。
そのうえで、頂点を増やすたびに、ある葉を選んだ時のスコアの伸びを都度更新することができればいいのですが、毎回DFSすると間に合いません。何とかしてさぼれないか考えます。
さて、ある葉を選ぶ、ということが木に対してどういう変化をもたらすのか観察してみましょう。ある葉を選ぶことで、実質的にその葉と根までの頂点が全て削除され、残った頂点と辺による部分木で構成される森になることがわかります。
この森の中で最もスコアを伸ばせる葉、すなわち各木の頂点から葉までの合計スコアが最もを選べばよいのですが、このままでは削除操作後の各木においてDFSをする必要があるのでもう少し工夫が必要です。
ここで問題を二つに分けましょう。
一つは、森の中で最もスコアの伸びが大きい葉を持つ木を選ぶ方法と、
一つは、それぞれの木の中で最もスコアの伸びが大きい葉を選ぶ方法です。
後者がわかれば、各木のスコアの伸び量の最大値を求めることができますから、あとはヒープなどに格納することによってどの木を選ぶべきかを高速に求めることができます。
さてこの後者について、
今まで根→葉までのスコア合計を葉側で持ち都度計算する、というイメージでしたが、各木において必要なのは最大の値のみであることを踏まえ、葉→根のイメージでとらえてみます。
すなわち、各頂点において、自分を頂点とする部分木において葉を選んだ時のスコアの最大伸び量※がわかればよいです。これは、事前計算としてDFSを行い、帰りがけで最大値を更新していくことで求めることができます。
この値はあくまで葉側からたどっていった最大値なので、頂点を増やしたとしても変化することはありません。従って使いまわすことができます。
削除の操作についてですが、ある木をヒープから取り出して選んだあとで、根から葉まで頂点をたどっていきます。この際、DPの復元の要領で※の値-頂点のスコアに一致する子を選んでいき、選ばれなかった子の頂点については候補となる木としてヒープに入れていきます。
以上を実装することでACでした。
おわりに
最初に文章だけ書いて超絶わかりにくいなと思ったので図を足しにしたらマシになった気がします。グラフ問題は絵をかいてなんぼなのかなと思いました。あとやっぱり全完は気持ちいいです。