2024/2/29 〜 2024/3/3 に開催された所謂 ICPC playoff (https://icpc.asia/) に、早稲田大学のチーム「hot-k-k1」のコーチとして参加しました。 選手としてではなくコーチとして参加した記録になります。 出発前までの作業 参加意思の確認 ICPC Asia Yokoha…

次数 1 の頂点の色 $c$ を固定した時の問題を $O(N)$ で解く方法です。 次の動的計画法を考えます。 - $\mathrm{dp}[u]:=$ 頂点 $u$ を根とする部分木の中で、次数 1 の頂点の色が全て $c$ であるものの通り数。 - $\mathrm{dp}_2[u]:=$ 頂点 $u$ を根とする…