Educational Codeforces Round 180 (Rated for Div. 2)

　Dまで。

　Bは難しい方法で解いてしまったが、単調増加や単調減少だとダメだけど、そうでなければ一回、という簡単な解法があった。単調増加or単調減少じゃないなら、山や谷の箇所があるので、確かに、という感じだが、気付かなかった。

コンテストへのリンク

コンテスト後のツイート

C 難しかった。最大値を使うかどうかで場合分けした。使うときは残り二個全探索。使わないときは、大きい二個(b,c)全探索で、残り一個aがa>MAX-b-cかつa>c-bなら良い。この個数は二分探索で求められる。
D degreeが2の頂点があるのが必要十分。そこだけ一直線にして、あとは交互に向き付け。

— titia (@titia_til) June 23, 2025

E. Tree Colorings

　根以外で枝分かれのない木の場合はコンテスト中にできていて、その場合は、素因数分解して、x*y*zなら、1+x/2+y/2+z/2みたいに求まる。

　それを応用して解こうと思ったが、結構苦労してしまった。

 木を、根からではなく、葉から作っていこう、と考えると良い。

・木Aと木Bを根同士を合わせる形で合体させると、node数はその和-1で、mの値はその積のような木になる。

・木に親をつけると、mの値は+2する。

　この二つの遷移でDPすればOKでした。