まず根を 1 つ固定して考える。すると、頂点 x を用いるならば、x の親の頂点 y を用いるという制約がある上でできるだけスコアが大きくなるように頂点集合を選ぶ問題になる。 これは典型最小カット問題 (燃やす埋める問題) なので、最大フローを計算するこ…