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