集训队作业-p捉羊计划

外国语学校题意简述给出一棵含N个结点的树。现在你有K个机器人，它们会从某一个结点出发，要求每条边至少被一个机器人遍历一次，最后每个机器人都可以停在任何一个结点。依次输出以每个结点作为出发点时，所有机器人的移动路线长度之和的最小值。限制：N≤15000，K≤30，每条边的长度不超过100。有30%的数据满足K≤2。样例如图，N=4，K=3。123410781若出发点为1，则最优方案是：1号机器人：1→2，长度为10。2号机器人：1→3，长度为7。3号机器人：1→4，长度为8。总长度为25。2341078样例如图，N=4，K=3。若出发点为2，则最优方案是：1号机器人：2→1→3→1→4，长度为32。2号机器人：停留在出发点。12

3

4107813号机器人：停留在出发点。总长度为32。2341078样例如图，N=4，K=3。12

3

410782108若出发点为3或4，则最小的总长度都是32。程序应输出25，32，32，32。1

13

4

2

34107

78出题思路本题是2002年克罗地亚的一道信息学竞赛题的加强。原题规定共有2个机器人，且这两个机器人的出发点是给定的。由于问题的特殊性，存在一个简单的线性算法。经过加强后，一共有K个机器人，且要依次计算出以每个结点作为出发点时的最小总代价。点树型动态规划泛化物品的合并对树的转化（拆点）算法分析因为问题的规模较大，所以想到树型动态规划。下面提到的前三个算法通过依次枚举每个结点作为机器人出发的结点，然后以该结点作为这棵树的根进行动态规划来求得答案。在下面的分析中，用p[x]表示结点x的父亲，用w[x]表示x与p[x]之间的边的长度。特别地，若x为根，那么p[x]=x，w[x]=0。算法一用f[x][i][j]表示有i个机器人由p[x]进入了以x为根的，最后有j个机器人回到p[x]的最小总代价。每做一次动态规划的时间复杂度为O(NK5)，于是总的时间复杂度高达O(N2K5)，期望得分为20分。算法二注意到一个性质：最优方案一定不会出现有若干个机器人进入以x为根的

后，有至少2个机器人返回p[x]的情况（除非x是根）。于是算法一中的f[x][i][j]只要计算满足0≤j≤1的状态。每做一次动态规划的时间复杂度为O(8NK2)，总的时间复杂度为O(8N2K2)=O(N2K2)。这个算法的常数比较大，期望得分为35分。算法三通过进一步的分析，还可以发现一个性质：在最优方案中，如果有至少2个机器人进入了以x为根的停在以x为根的，那么这些机器人都应该内。这启发

从“最后每棵

内停了多少个机器人”入手重新思考。算法三观察右边的图：K=3，黄色的结点表示机器人最后停留的位置。q=LCA(a,

b,

c)，p=LCA(a,

b)于是x到q的路径要走3次，q到p的路径要走2次，p到a、p到b、q到c的路径要走1次，其它的边要走2次。xqpc311a11b2算法三用f[x][i]表示最后有i个机器人停在以x为根的

中，最小的总代价是多少。设x的孩子为x1、x2、……、xm，则f

[x][i]

min{

f

[x1

][i1

]

……

f

[xm

][im

]}

s(x,i)间的边的代价，即s(x,i)

w[x]

2i

0

w[x]

i i

0其中i1

i2……

im

i，s(x,i)表示x与p[x]之算法三在多叉树上的动态规划，需要采用左孩子右兄弟表示法或对结点的所有孩子进行二次动态规划。这里以后者为例。用g[n][i]表示最后有i个机器人停在以x的前n个孩子为根的中的代价，即2

2g[n][i]

min{

f

[x1

][i1

]于是f

[x][i]

g[m][i]

s(x,i)算法三状态转移方程为在这个算法中每次转移就是将两个泛化物品g[n-1][]与f[xn][]合并。每做一次动态规划的时间复杂度为O(NK2)，因此总时间复杂度为O(N2K2)，与算法二相同，但常数要小得多，期望得分为50分。0g[n][i]

min{g[n算法四前三个算法因为需要先枚举出发点，所以时间复杂度无法摆脱O(N2×Km)的形式。题目的限制中提到共有30%的数据满足K≤2。利用算法三的思想（从机器人停留的位置入手）对这两种特殊的情况进行分析，可以得到一个时空复杂度均为O(N)的算法，期望得分为30分。如果将这个算法和算法三结合，那么可以得到70分。算法五要得到时间复杂度较低的算法，就要避免在枚举出发点后对整棵树重新进行动态规划。由算法三

发现，这个问题其实就是不断地合并泛化物品。算法五用f[x][y]表示将边(x,y)删去后，以x为根的的泛化物品。计算f[x][y]需要将x除了y以外所有相邻结点的泛化物品合并。xyx1x2x4x3算法五如果以x作为机器人的出发点，那么将与x相邻的结点的泛化物品合并就可以得到答案。xxmx1x2x4x3……算法五设M为所有结点的度的平方和，那么总的时间复杂度为O(MK2)。该算法的时间复杂度是和每个结点的度的平方和有关的，所以算法的时间效率会受到树的形态的影响。如果某些结点的度特别大，那么这个算法的时间复杂度会接近O(N2K2)。期望得分为65分。算法六算法五对于较糟糕。要避免情况比，y1y2xa1a2am0000ym就要保证每个结点的度不能太大。这可以通过

x1“拆点”来解决。如图，结点x共有m个孩子，那么可以转化为x2xmxa1a2am……x1x2xm算法六xa1a2am……x1x2xmy1y2xa1a2am0000ym先将这棵树转化成有根树，然后对于每个非叶结点，将它所有的孩子串在一个链表上，就可

x1以保证每个结点的度不超过3。这就相当于把结点x“拆”成了结点x、y1、y2、……、ym。x2xm算法六y1y2xa1a2am0000ym从图中可以看出，若结点x有m个孩子，则需要再增加m个结点，所以经过这种转化后总结点数

x1仍为O(N)级别。这时再套用算法五，就可以得到一个时间复杂度为O(NK2)的算法，可以得到满分。x2xm数据生成方法共有三种数据：A类型：完全随机的数据。每次随机选出两个结点，用并查集判断是否连通，如果不连通则连上这条边。A类数据占40%，集中在中小规模的数据。B类型：与A类似，但是记录了每个结点的度，如果某个结点的度达到了D则不能再连边。可以生成近似于链状的数据。B类数据占25%，集中在中小规模的数据。数据生成方法C类型：先随机选出D个结点，之后与A类似，但每次随机选结点的时候会有80%的概率优先选中这D个结点中的某一个。这类数据可以控制某些结点的度特别大，使得算法五超时。C类数据占35%，集中于大规模数据。算法一依次枚举每个结点作为机器人出发的结点，然后以该结点作为这棵树的根进行动态规划。用f[x][i][j]表示有i个机器人由p[x]进入了以x为根的，最后有j个机器人回到p[x]的最小代价。算法一xi1j1i2

j2im……jmi

jx1x2xm设x的孩子为x1、x2、……、xm，则f

[x][i][

j]

min{

f

[x1

][i1

][

j1

]

……

f

[xm

][im

][

jm

]}

w[x]

(i

j)其中jk≤ik≤i，i

i1

j1

i2p[x]

j2

……

im

jm

j算法一对应的方案为：有i个机器人由p[x]进入x；有j1个机器人进入x1后返回x，有j2个机器人进入x2后返回x，……，有jm个机器人进入xm后返回x；有i1-j1个机器人进入x1后不返回，有i2-j2个机器人进入x2后不返回，……，有im-jm个机器人进入xm后不返回；最后有j个机器人由x回到p[x]。p[x]xii1j1i2

j2im……jmjxx1

2xm算法一在多叉树上进行动态规划，需要采用多叉转二叉或对结点的所有孩子进行二次动态规划。用g[n][i][j]表示共有i个机器人进入以x的前n个孩子为根的，最后有j个孩子回到x的最小代价，即g[n][i][

j]

min{

f

[x1

][i1

][

j1

]

……

f

[xn

][in

][

jn

]}其中jk≤ik≤i算法一状态转移方程为g[n][i][

j]

min{g[n

1][i0

][

j0

]

f

[xn

][in

][

jn

]}其中j0≤i0≤i，jn≤in≤i，因为在计算g[n][i][j]时需要枚举i0、j0、in，所以转移的时间为O(K3)，而状态数为O(NK2)，所以每做一次动态规划的时间复杂度为O(NK5)，于是总的时间复杂度高达O(N2K5)。p[x]xiinjnji0j0……x1

x2xn算法二的证明性质：最优方案一定不会出现有若干个机器人进入以x为根的

后，有至少2个机器人返回p[x]的情况（x是根的情况除外）。算法二的证明如图，设有两个机器人的移动路线分别为p[x]→x→A→x→p[x]和p[x]→x→B→x→p[x]，那么可以把一个机器人的移动路线改为p[x]→x→A→x→B→x→p[x]，另一个机器人则是停在p[x]，效果相同，但(p[x],x)这条边可以少走两次，于是得到了一个更优的方案。p[x]xABp[x]xAB算法二经过这个转化后，可以发现算法一中的f[x][i][j]只需要计算满足0≤j≤1的状态。于是，这个算法的空间复杂度降到了O(2NK)=O(NK)。每做一次动态规划的时间复杂度为O(8NK2)，总的时间复杂度为O(8N2K2)=O(N2K2)，常数比较大。算法三的证明性质：在最优方案中，如果有至少2个机器人进入了以x为根的都应该停在以x为根的，那么这些机器人内。算法三的证明如图，设有两个机器人的移动路线分别为p[x]→x→A→x→p[x]和p[x]→x→B，那么可以把一个机器人的移动路线改为

p[x]→x→A→x→B，另一个机器人则是停在p[x]，效果相同，但(p[x],x)这条边可以少走两次，于是得到了一个更优的方案。p[x]xABp[x]xAB算法三由这个性质可知，算法一中的f[x][i][j]只需要计算满足i=j=1和i≥1且j=0的状态。于是，对于两个有效的状态(i1,j1)和(i2,j

)，如果i1≠i2或j1≠j2，那么i1-j1≠i2-j2，所以可以把i和j压缩成一维，用f[x][i-j]来代替原来的f[x][i][j]，从而同时减少了时空复杂度的常数。因为i-j表示最后停留在以x为根的

内的机器人的数量，所以这可以看做算法三的另一种解释。泛化物品（以下内容引自dd_engi《背包问题九讲》）考虑这样一种物品，它并没有固定的费用和价值，而是它的价值随着你分配给它的费用而变化。这就是泛化物品的概念。更严格的定义：在背包容量为V的背包问题中，泛化物品是一个定义域为0..V中的整数的函数

h，当分配给它的费用为v时，能得到的价值就是h(v)。这个定义有点抽象，另一种理解是一个泛化物品就是一个数组h[0..V]，给它费用v，可得到价值h[v]。泛化物品的和面对两个泛化物品h和l，要求用给定的费用

v从这两个泛化物品中能得到的最大价值，只需枚举如何将费用如何分配给两个泛化物品就可以了。同样的，对于0..V的每一个整数v，可以求得费用v分配到h和l中的最大价值f(v)，也即f

(v)

max{h(k)

l(v

k)

|

0

k

v}泛化物品的和可以看到，f也是一个由泛化物品h和l决定的定义域为0..V的函数。也就是说，f是一个由泛化物品h和l决定的泛化物品。由此可以定义泛化物品的和：h、l都是泛化物品，若泛化物品f满足前面提到的关系式，则称f是h与l的和。这个运算的时间复杂度取决于背包的容量，是O(V2)。泛化物品的和泛化物品的定义表明：在背包问题中，将两个泛化物品代以它们的和不影响问题的答案。事实上，对于其中的物品都是泛化物品的背包问题，求它的答案的过程也就是求所有这些泛化物品之和的过程。设此和为s，则答案就是s[0..V]中的最大值。算法四当K=1时，设出发点为x，机器人最后停在y，那么x到y的路径（红色边）要走1次，其它的边（蓝色边）要走2次。用S表示所有边的权值之和，d(x)表示离x最远的结点与x的距离，那么若出发点为x，则最小的总代价为2S-d(x)。求d(x)是一个经典的树型动态规划问题，时间复杂度为O(N)。xy算法四设所有边的权值之和为S，树上相距最远的两个结点间的距离为D，那么最小的总代价为2S-D。xaz当K=2时，设出发点为x，两个机器人最后分别停在y和z。设a=LCA(y,z)，那么y到z的路径（红色边）要走1次，而其它的边（蓝色边）要走2次。y算法四有趣的是，当K=2时，可以发现无论以哪个结点作为出发点，最小代价都是相同的。求D的方法很多，其中

法是利用K=1时的中间结果，D就是所有d(x)的最大值。于是，当K=2时，

也得到了一个时间复杂度为O(N)的算法。这也是原题的做法。算法四的补充对于每个结点x，求出以下几个值：d1[x]表示x到以x为根的中的结点的距离的最大值，t[x]表示以x为根的

中离x最远的结点在以x的哪个孩子为根的

中，d2[x]表示x到在以x为根的

中但不在以t[x]为根的

中的结点的距离的最大值。d1[x]，t[x]，d2[x]可以通过一次O(N)的树型动态规划求出。p[x]xt[x]d1[x]d2[x]算法四的补充用u[x]表示x到不在以x为根的

中的结点的距离的最大值，则u[x]

max{u[

p其中可以在O(N)的时间内求出所有的d(x)。h(x)

d1[

p[x]]x

t[

p[x]]x

t[

p[x]]d

[

p[x]]

2p[x]xh(x)u[p[x]]w[x]算法五的时间复杂度用f[x][y]表示将边(x,y)删去后，以x为根的的泛化物品。计算f[x][y]需要将x除了y以外所有相邻的结点的泛化物品合并。设结点x的度为dx，那么求f[x][y]的时间复杂度为O(dxK2)，因此计算f[x][]的时间复杂度x设M为所有结点的度的平方和，那么计算f的时间复杂度为O(MK2)。为O(d

2

K2

)。算法五的时间复杂度如果以x作为机器人的出发点，设与x有边直接相连的结点为x1、x2、……、xm，令Fx为将f[x1][x]、f[x2][x]、……、f[xm][x]合并后得到的泛化物品，那么Fx[K]就是答案。计算Fx需要进行dx-1次合并泛化物品的运算，因此时间复杂度为O(dxK2)。因为以每个结

点为出发点都要计算一次，所以时间复杂度为O(NK2)。结合前面的预处理，该算法的总时间复杂度为O(MK2)。算法五的空间复杂度虽然f[x][y]似乎需要占用O(N2K)的空间，但

x与y的搭配只有O(N)种，所以具体实现时可以给每条边一个唯一的序号（注意边(x,y)和边(y,x)应该被视为不同的边），那么空间复杂度就是O(NK)。算法七除了算法六中使用的“拆点”的技巧之外，还有一种算法也可以达到O(NK2)的时间复杂度。先随意取一个结点作为根，进行一次动态规划。算法七p[x]xU[x]表示删去边(p[x],x)后以p[x]为根的的泛化物品。U[x]L[x]R[x]D[x]算法七p[x]xL[x]表示将x左边的兄弟合并后得到的泛化物品。U[x]L[x]R[x]D[x]算法七p[x]xR[x]表示将x右边的兄弟合并后得到的泛化物品。U[x]L[x]R[x]D[x]算法七p[x]xD[x]表示将x的所有孩子合并后得到的泛化物品。U[x]L[x]R[x]D[x]算法七p[x]x计算U[]、L[]、R[]、D[]的时间复杂度都是O(NK2)。U[x]L[x]R[x]D[x]算法七p[x]x枚举出发点x，将U[x]、L[x]、R