一道神仙题
首先考虑如何记录当前的状态。我们发现如果记录警察所处点的话,就需要记录犯人在这个点各个子树内的分布情况,显然是记不下的。那我们考虑就记录警察在哪条边上。
令dp[e][tot][cnt]代表当前在走e这条边,朝向的这个部分有cnt个犯人,总共还有tot个犯人,全部解决的时间。
那我们考虑警察走完了这条边e,到达v之后会如何决策(警察已经得到了犯人们在v子树内的分布情况,ai代表v的第i个儿子的子树分了多少个犯人)。自然是选择一个son,使得dp[eson][tot][a[i]]最小。
而犯人的最优决策就是选择一种分配方式,使得∑a[i]=cnt且min(dp∀son[eson][tot][a[i]])最大。考虑可以二分这个最小值然后用这个最小值来更新现在的DP值即可。
有一种特殊情况就是当走到了叶子必须原路返回,如果原来是dp[e][tot][cnt],那就从dp[e1][tot−cnt][tot−cnt]转移过来。
状态的复杂度O(n2m),加上转移复杂度,总复杂度就是O(n2m2log)。