一道用了两次背包的图论题

DP的时候需要枚举环长，即在每次枚举中将环上的一个点的父亲（后继）改成1，而此时我们认为环长是一个预先确定的数。例如，在题图中，我们枚举到将2挂在1上，就认为环长是2，将3挂在1上环长就是3.但这样计算出的环长并不一定是真实的环长，例如，当枚举将3挂在1上（环为123）时，DP的最优决策有可能是将2挂在1上，从而环长就是2而非3.但这并不会影响结果，因为按照环长为3计算，最终除以的数要大一些，从而结果会更小，即“在枚举到环为123时的最优决策中把2挂在1上”计算出来的R(1)一定没有“枚举到环为12时(把2挂在1上)的最优决策”的R(1)大。
另，这道题的背包不是经典01背包，不能把“对每个点分配0,1，...，M次修改机会”当做单独的物品，因为它们之中只能取一个，所以实际上是分组背包

Gold Miner!