最近のインタビューで、次の質問がありました。サイクルのない双向グラフGがあります。各エッジにはある程度の重みがあります。また、（いくつかのエッジを削除することによって）互いに切断する必要があるノードKのセットがあります。Kセット内の任意の2つのノード間には1つのパスしかありません。目標は、削除されたエッジの総重量を最小限に抑え、すべてのノード（セットKから）を相互に切断することです。
私のアプローチは、Kセットから各ノードに対してBFSを実行し、Kからのノードのすべてのペア間のすべてのパスを決定することでした。したがって、パスのセットがあります（各パスはエッジのセットです）。次のステップは、動的計画法を適用して、削除されたエッジの最小総重量を見つけることです。そして、ここで私は立ち往生しました。DPがどのように行われるべきかについて私を助けてくれませんか（私に指示してください）。
ありがとう。