# 22 条题解

• @ 2020-05-24 12:35:10

这题好坑啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊······（省略N字）

``````
#include<cstdio>
#include<cctype>
#define N 4005
#define max(A,B) ((A)>(B)?(A):(B))
#define min(A,B) ((A)<(B)?(A):(B))

int val[N];
int deg[N];
int sum[N];
int cnt,n,m;
int f[N][505];
int g[N][505];
int son[N][N];

int getint() {
int x=0;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}

void dfs1(int now){
sum[now]+=val[now];
for(int i=1;i<=son[now][0];i++){
int to=son[now][i];
for(int j=0;j<=m;j++)
f[to][j]=f[now][j];
sum[to]=sum[now];
dfs1(to);
for(int j=1;j<=m;j++)
f[now][j]=max(f[now][j],f[to][j-1]+val[to]);
}
}

void dfs2(int now){
for(int i=son[now][0];i;i--){
int to=son[now][i];
for(int j=0;j<=m;j++)
g[to][j]=g[now][j];
dfs2(to);
for(int j=1;j<=m;j++)
g[now][j]=max(g[now][j],g[to][j-1]+val[to]);
}
}

signed main() {
n=getint(),m=getint();
for(int i=1;i<=n;i++) {
if(i==1){
getint(),val[1]=getint();
continue;
} else {
int a=getint();
son[a][++son[a][0]]=i;
val[i]=getint();
}
}
dfs1(1);
dfs2(1);
int ans=0;
for(int i=1;i<=n;i++){
if(son[i][0])
continue;
for(int j=0;j<=m;j++)
ans=max(ans,f[i][j]+g[i][m-j]+sum[i]);
}
printf("%d\n",ans);
return 0;
}

``````
• @ 2017-08-25 15:35:34

const
maxn=4040;
maxk=550;
var
fl,fr:array[0..maxn,0..maxk]of longint;
v:array[0..maxn,0..maxn]of longint;
a,sum,f:array[0..maxn]of longint;
n,k,ans:longint;

function max(x,y:longint):longint;
begin
if x>y then exit(x);
exit(y);
end;

procedure dfsl(x:longint);
var
i,j:longint;
begin
sum[x]:=sum[f[x]]+a[x];
for i:=1 to v[x,0] do
begin
for j:=0 to k do
fl[v[x,i],j]:=fl[x,j];
dfsl(v[x,i]);
for j:=1 to k do
fl[x,j]:=max(fl[x,j],fl[v[x,i],j-1]+a[v[x,i]]);
end;
end;

procedure dfsr(x:longint);
var
i,j:longint;
begin
for i:=v[x,0] downto 1 do
begin
for j:=0 to k do
fr[v[x,i],j]:=fr[x,j];
dfsr(v[x,i]);
for j:=1 to k do
fr[x,j]:=max(fr[x,j],fr[v[x,i],j-1]+a[v[x,i]]);
end;
end;

procedure main;
var
i,x:longint;
begin
for i:=1 to n do
begin
inc(v[f[i],0]);v[f[i],v[f[i],0]]:=i;
end;
dfsl(1);
dfsr(1);
for i:=1 to n do
if v[i,0]=0 then
for x:=0 to k do
ans:=max(ans,fl[i,x]+fr[i,k-x]+sum[i]);
writeln(ans);
end;

begin
main;
end.

• @ 2009-11-01 22:06:05

顶楼下~这篇论文是徐持衡。。。

其中重点看树形依赖背包（选课）

的优化。

但是有点不同的是这题有条免费路径

• @ 2009-11-01 20:03:41

建议先看看国际集训队有一篇介绍背包的论文，特别是泛化背包，理解了那个这题理解起来方便多了……

• @ 2009-11-01 15:39:54

巧妙的状态构建和treedp优化，看了很久才明白。

虽然程序极短。

• @ 2009-10-26 17:29:03

比赛的时候一看就知道做不来....于是看都不看了

本人乃不懂树的沙茶.....于是乎挥毫泼墨

写下几行大字：

var n:longint;beginwriteln(random(n*n)+1);end.

//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

• @ 2009-10-26 12:09:26

30分啊顶多。。。。。。。。。。。

多了个h限制，太难了。。。。。

• @ 2009-10-26 11:00:34

被虐了。不懂做

• @ 2009-10-25 15:15:33

陶陶就是LX那位神牛吧?

• @ 2016-12-25 15:59:21

摘苹果容易吃苹果难

• @ 2016-10-07 20:25:43

摘苹果容易吃苹果难

• @ 2016-03-07 19:21:40

摘苹果容易吃苹果难

• @ 2014-11-02 21:25:41

求讲解那条免费路径是什么情况

• @ 2014-08-05 19:57:10

摘苹果容易吃苹果难

• @ 2013-05-01 19:55:35

摘苹果容易吃苹果难

• @ 2009-10-31 16:30:16

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 9ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 9ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：18ms

哈 足够快了 算法O(NK)

• @ 2009-10-26 21:39:07

O(n*k^2)

前3点0ms，后7点超时……

无语ing...

TreeDp还能再优化吗？

附上我的程序：program P1676;var n,i,j,k:longint; c,h:array[1..4000] of longint; g:array[0..4000,-1..500,0..1] of longint; t:array[0..4000,0..1] of longint;procedure deep(p,q:longint);var i:longint;begin if p=0 then exit; h[p]:=q; deep(t[p,0],q+1); deep(t[p,1],q);end;function dp(p,q,r:longint):longint;var i:longint;begin if (p=0) or (q

• @ 2009-10-26 19:03:28

O(N*K^2） +卡时。。

本来指望拿个40--50.。结果全部答案错误。可见我沙茶。

昨天调了2.5小时的TreeDp。。

结果。。O.O

• @ 2009-10-25 18:26:36

= =

占个楼先

• @ 2009-10-25 16:32:29

ORZ陶陶神牛

http://blog.sina.com.cn/s/blog_5dafc7f00100fopg.html

陶陶最近又长了两颗小牙齿，总共有十颗了。小宝贝喜欢吃有些硬度的食物，饼干、馒头、苹果……，尤其是苹果，她不需要我们给她弄成苹果泥了，她喜欢苹果片。

我喜欢看陶陶吃苹果的样子。她拿着奶奶削好的苹果片，慢慢的放到嘴边，然后用小牙“咔嚓”咬下苹果片的一大块，发出脆脆的声音。这时，她抬头看看我，好像在对我说“妈妈，我自己吃到苹果了，真好吃！”我冲她笑笑，她也回敬我一个笑脸。可是，陶陶吃苹果并不总是这么乖。她有时吃的带劲了，一口接着一口的咬，结果嘴里的苹果还没咽下去，又吃一口，嘴里的苹果太多了，转不开个了，小家伙就急得“嗷嗷”大叫。即使这样，她也决不允许我们把她嘴里的苹果弄出来，有时真让我们着急。

陶陶是我的精灵，她带给我的快乐是永远不会忘记的！

ID
1676

9

986

68

7%

1