Codeforces Round 862 (Div. 2)

　Cまで三完。Dで全方位木DPを使おうとしたら分からなくなって混乱していた。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round 862 (Div. 2)のD、それぞれの頂点について、最も遠い葉までの距離を求めれば良いよね。それは、https://t.co/uUv7bS0LNu
に書いてあるから全方位木DPだよね。
よし、色々忘れているし久しぶりに全方位木DPに向き合う（復習する）かーと思ったら、分からなくなって解けずに終わった。

— titia (@titia_til) April 2, 2023

D. A Wide, Wide Graph

　全方位木DPでAC。復習になった。（結局、以前の自分の実装を元に書き直した）

　今の自分の実装（カッコ内は自分の実装での命名）では、

・単位元（unit）

・子たちの値をmergeするときの関数（compose_calc）

・子たちから計算した値からそのnodeについての値を出す関数（final_ans）

・子たちが存在しないときに入れておく値（no_composed_value）

　を決めれば答えが求まるようになっていると思う。多分、mergeの可換性も必要……というか、可換じゃない場合の求め方を理解できていない気がする。

　ただこの実装、四つ目が気持ち悪いねぇ……。なんとかしたい。

　全方位木DPが分かりにくいと思うのは、私が、「ある頂点に関する部分木に関するDP」ではなく、「辺に関するDP」だと思っているせいが大きい。

　私の実装では、UP[x], DOWN[x]で、「xとxの親を結ぶ辺」について、それぞれ、「子から親方向に見たときのDPの値」「親から子方向に見たときのDPの値」と考えている。

　ただ、これだとDOWN[x]の値が直感と一個ずれる（その親に関する部分木を考えているため）んだよね。だけど、一個ずらしてDPテーブルを定義したらもっと（自分には）もっと分かりにくくなってしまった。

　このあたりが毎回混乱の原因になっています。