Codeforces Round #595 (Div. 3) - F. Maximum Weight Subset
概要
サイズNの木が与えられて、それぞれの頂点には重みがweight[i]だけ設定されている。
あなたは、この中から次の条件を満たすように、好きなだけ頂点を選べる。選んだ頂点たちの重みの総和の最大値を求めよ。
- 選んだ頂点たちはお互い距離がK+1以上離れている。
概要： 1 <= N, k <= 200
ACするまで
1. sizeが200前後だから、3乗まで許容されるDPとか全探索とかでは？
2. 全探索 or DPで解けそう。
3. お互いに距離がK+1以上という条件をDPで扱うにも、木の上とか順番とかいろいろあって難しい。
4. 木DPのメリットとして、親方向からたどっていく方向は制約に入れなくてよい。というのがある。子供との間での距離を考えればよい。
5. また、これはナップサックのように、距離に関しては、a以上のものならすべてOKということがあるので、そのように実装する。
6. AC
考察
この問題では、公式解説ではが最適だとされているが、
の解法もある。そちらではまだ勉強ができてないのだが、できたら追記したい。
公式解法
制約的な意味でも、DPなどを最初に思いつくだろう。
Point
木DPは、親方向の制約をかんがえなくてよい(それはそう)。
お互いに距離がK+1以上であるが、木DPで考えていくのならば、親方向を考えずに、子供方面の選んだものからの距離だけを考えればよい。
また、もらうDPで計算するとき、「距離がi離れてる」は「距離がi+1離れている」を包含しているので、ナップサックのDPと同じように、「以上」を定義に盛り込んでおく。
dp[v][i] := 頂点vを頂点とした部分木において、子供方向の次に選んだ頂点までの距離の最小値がi以上の時の weightの合計の最大値
ここで、頂点vを選ぶor選ばないで考えよう。
頂点vを選ぶのなら、dp[v][0]である。(最後に選んだのからの距離が0)
子供方向で、今のvから距離がK+1以上離れているものを選べばよい。
まず、dp[v][0] += weight[v]とできる。(自分自身のweight[v]を加算)
子供をsonとすると、dp[v][0] += dp[son][K]と加算できる。(子供同士は必ず距離K+1以上離れている)
選ばない(dp[v][1 ~ K])のならば、少し複雑になる。
この時、遷移するときに、着目してるのを除きすべての子供につい、てdp[son][max(i-1, k-i)]を足す、ということをしているが、これは1回すべての子供のそれを足しておいて、毎回いらない分を引くということで、O(1)で遷移できる。
計算量を分析すると、
1. DFSですべての頂点を見る。
2. 各頂点について、最後に採用した深さがi(以上)のiを考える。
3. その中での遷移で、子供を1つ着目するため、すべての子供を見る。
4. その子供方向から伸びたのを計算する。(O(N)かかるが、O(1)で短縮可能)
一見4重(3重)ループになるが、1と3について、根つき木は、親と子のセットはN-1組しか存在しないので、実は(4のループの高速化をしなくても)ではなく、
である。
一言
木DPの習熟度が足りん。実装力も足りん。
Special Thanks
以下の記事を大いに参考になりました。このような素晴らしい記事を書き上げた方に多大なる感謝と敬意を表します。
在我写这篇解说时，下面的三篇文章对我大有帮助。在这里对提供如此平易近人的讲解的诸位，表示衷心的感谢。
まとめ
Point
木DPは、親方向の制約をかんがえなくてよい(それはそう)。
