けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

実は一次元で済む二次元DP

AtCoder AGC 029 E - Wandering TKHS (1200 点)

またしても、最後の最後がよく詰めきれず... (でもその最後のところの詰めの大変さが、この難易度帯の特徴なんだよね) 問題へのリンク 問題概要 頂点のツリーが与えられる。根ノードの番号を 1 とする。各ノード について、以下のクエリに答えよ: 初期状態を…