### [题解]ZOJ Monthly, May 2011 » ZOJ3506

ZOJ3506.cpp

```#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

const int MAXN = 1024;
const int MAXM = 24;
const int INF = 1000000007;

int n, m, v[MAXN];
vector<int> e[MAXN];
int d[MAXN], dp[MAXN][MAXM];

void gao(int s, int p) {
e[s].erase(remove(e[s].begin(), e[s].end(), p), e[s].end());
d[s] = 0;
dp[s][0] = 0;
fill(dp[s] + 1, dp[s] + 1 + m, INF);
for (vector<int>::const_iterator t = e[s].begin(); t != e[s].end(); ++t) {
gao(*t, s);
d[s] += d[*t] + 1;
for (int j = m; j >= 0; --j) {
dp[s][j] += dp[*t][0];
for (int k = j - 1; k >= 0; --k) {
dp[s][j] = min(dp[s][j], dp[s][k] + dp[*t][j - k]);
}
for (int k = 1; k <= d[*t] + 1 && k <= j; ++k) {	// !!!
dp[s][j] = min(dp[s][j], dp[s][j - k]);
}
}
}
transform(dp[s], dp[s] + 1 + m, dp[s], bind2nd(plus<int>(), v[s]));
}

int gao() {
int y = INF;

gao(0, -1);
y = min(y, dp[0][m]);
if (m > 0) {
for (int i = 1; i < n; ++i) {
for (int j = 1; j <= n - d[i] - 1 && j <= m; ++j) {	// !!!
y = min(y, dp[i][m - j]);
}
}
}

return y;
}

int main() {
int a, b;

while (scanf("%d%d", &n, &m) != EOF) {
for (int i = 0; i < n; ++i) {
scanf("%d", &v[i]);
e[i].clear();
}
for (int i = 1; i < n; ++i) {
scanf("%d%d", &a, &b);
--a;
--b;
e[a].push_back(b);
e[b].push_back(a);
}

printf("%d ", gao());
for (int i = 0; i < n; ++i) {
v[i] = -v[i];
}
printf("%d\n", -gao());
}

return 0;
}

//Run ID 	Submit Time 	Judge Status 	Problem ID 	Language 	Run Time(ms) 	Run Memory(KB) 	User Name 	Admin
//748 	2011-04-27 04:57:21 	Accepted 	G 	C++ 	40 	296 	watashi@ArcOfDream 	Source
```
8 Responses to “ZOJ3506”
1. left_hand says:

弱问巫教，26行：

for (int k = j – 1; k >= 0; –k) {
dp[s][j] = min(dp[s][j], dp[s][k] + dp[*t][j - k]);
}
转移的时候为什么k不能等于j？
对于j的划分{k, j-k}, 不能有{j, 0}(k=j)这种划分么？ 子树cut 0次。

• watashi says:

dp[s][j] += dp[*t][0];
在这一句里了？

• left_hand says:

是的，我今天再看代码的时候注意到了。。。DP太弱了。谢谢

2. alpc86 says:

请问这组数据为什么您的程序跑出来是 -18 27
9 8
-13 7 -2 20 -18 13 -2 4 -8
1 3
1 4
1 5
1 6
1 9
3 7
4 2
9 8
我觉得应该是 -18 20

• watashi says:

看来是数据不够强，似乎第44行这里要改成
j <= n – d[i] – 1

我把这组数据加进去并rejudge了
thx

3. alpc86 says:

请问为什么这组数据您的程序跑出来的是-18 27？
9 8
-13 7 -2 20 -18 13 -2 4 -8
1 3
1 4
1 5
1 6
1 9
3 7
4 2
9 8
我的理解应该是-18 20

4. xww says:

很经典的dp吗？思路和代码我看不太懂啊。能不能说的更详细点啊？？或者推荐一下相似经典dp题目。 很感谢。因为很想把这题搞懂啊。

• watashi says:

DP套DP的树形DP的题吧，记得09年的合肥Regional就有一道比较经典的，你可以找找看……

5.