家\(i\)に[入る/入らない]を決めて金額を最大化する問題です。家\(u\)に入ると家\(v\)に入らなければならないという制約が複数あるので燃やす埋める問題(Project Selection Problem)とみなすことができます。

このタイプの制約がある問題は以下の記事と同様に考えることができます。 https://kanpurin.hatenablog.com/entry/2022/09/02/190700