Codeforces Round 1000 (Div. 2)

　Dまで四完。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round 1000 (Div. 2) Dまで。
A 注意すべきはl=r=1だけ？
B 左右のどちらかから貪欲に取る
C 次数が大きいものを何個か試し、残った中で次数が最大のものを削除、でACした。
D A,Bとも左右の端から貪欲に取る。A側の頂点が足りなくなったら、AABの三角形を一つ削除、とやっていく。

— titia (@titia_til) January 22, 2025

E. Triangle Tree

　苦労したが、公式解説など色々参考にしてAC。

　まず、木DPでできそう、と思ってしまったのが筋が悪かった。

　主客転倒的な考え方でいくべきだった。

　その後は、うーん、どうすれば良かったんだろう。

　min$(d_u$, $d_v)$ の総和と、$d_{LCA}$の総和に分けて考えれば良い、というのは立式を見れば分かるが、その時点でちょっと思いつきにくい。

　さらに、それぞれの求め方も簡単とは言えず……。

　とはいえ、立式し、式を簡単な形に分解しようと思う部分は自然。

　その後、主客転倒でいこう、と思えるかどうかが勝負なのかな。