Codeforces Round 899 (Div. 2)

　Cまで三完。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round 899 (Div. 2) 全方位木DPの書き方が下手＆高速化できないためDが解けず。
A 実際に作ってみた。
B k=1～50それぞれを使わない場合の全探索
C ある数を取ったらそれ以降の（正の）もの全てを取れる。
D 全方位木DP。部分木全てを0/1にするコストを持つ。他に部分木サイズが必要。

— titia (@titia_til) September 25, 2023

D. Tree XOR

　解法ツイートを見た。コンテスト中はbitごとに全方位木DPする方法しか思いつかなかったが、bitごとにやらずにできる。

　辺ごとの寄与を考える。辺に両端の頂点のxorを書き込んでおくと、その両端の二頂点を一致させるためには、「その値*葉の方の頂点の個数」のコストがかかる。これを全方位木DPで求めればOK。（さらにいうと、全方位木DPもいらないらしい）

　bitごとにやろうとしたときの全方位木DPはなかなか書きにくかったが、こちらの全方位木DPは実装も素直でした。