ferinの競プロ帳

競プロについてのメモ

2019-01-13から1日間の記事一覧

エイシング プログラミング コンテスト 2019 E - Attack to a Tree

問題ページ 解法 木DPをする。dp[v][i][j] = (頂点vを根とする部分木でi回辺を切っていて頂点vの連結成分以外は問題文の条件を満たし、頂点vの連結成分が全てバッテリー(j=0)orそれ以外(j=1)のときの連結成分の頂点の重みの和の最小) とする。不可能な場合は…