CF868E Policeman and a Tree

一道神仙题

首先考虑如何记录当前的状态。我们发现如果记录警察所处点的话，就需要记录犯人在这个点各个子树内的分布情况，显然是记不下的。那我们考虑就记录警察在哪条边上。

令$dp[e][tot][cnt]$代表当前在走$e$这条边，朝向的这个部分有$cnt$个犯人，总共还有$tot$个犯人，全部解决的时间。

那我们考虑警察走完了这条边$e$，到达$v$之后会如何决策（警察已经得到了犯人们在$v$子树内的分布情况，$a_i$代表$v$的第i个儿子的子树分了多少个犯人）。自然是选择一个$son$，使得$dp[e_{son}][tot][a[i]]$最小。

而犯人的最优决策就是选择一种分配方式，使得$\sum a[i]=cnt$且$min(dp_{\forall son}[e_{son}][tot][a[i]])$最大。考虑可以二分这个最小值然后用这个最小值来更新现在的DP值即可。

有一种特殊情况就是当走到了叶子必须原路返回，如果原来是$dp[e][tot][cnt]$，那就从$dp[e^1][tot-cnt][tot-cnt]$转移过来。

状态的复杂度$O(n^2m)$，加上转移复杂度，总复杂度就是$O(n^2 m^2\log)$。