树上分组背包

题意:给定一棵n个节点的树,树的某个节点s上有k个机器人。要分配这些机器人去遍历这颗树,求经过的边的最小权值和。

分析:对于某一棵子树,如果进去一个机器人,它要么出来,要么不出来。如果有一个机器人出来了,就不能有第二个机器人出来。因为让第一个人去走第二个人要走的路,比第二个人自己走再走出来肯定要优(证:如果第一个人单独走,走过的每一条边只经过两遍,如果两个人走一个人走的路,既然都要进去出来,那么出口处的路会经过4遍,比前者差,证毕)。因此第二个人就可以不进入这棵树。所以我们可以得到一个优美而且正确而且高效率的函数:

$f(i,j)$

$f(i,j)$表示i节点进去不出来j个机器人。如果j等于0的话表示进去一个人出来。所以有$f(i,j)=min(∑(f(k,l)+w(i,k))(∑l=j,(i,k)∈E))$,这其实就是一个分组的背包问题,物品是子节点的j值,每个子节点是一组,要达到当前节点j值同时最小化$f(i,j)$。于是时间复杂度为: $O(nk^2)$