这题好坑啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊······（省略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;
}

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
read(n,k);
for i:=1 to n do
begin
read(f[i],a[i]);
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.

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

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

的优化。

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

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

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

虽然程序极短。

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

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

写下几行大字：

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

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

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

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

被虐了。不懂做

陶陶就是LX那位神牛吧?

摘苹果容易吃苹果难

摘苹果容易吃苹果难

摘苹果容易吃苹果难

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

摘苹果容易吃苹果难

摘苹果容易吃苹果难

编译通过...

├ 测试数据 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)

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

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

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

昨天调了2.5小时的TreeDp。。

结果。。O.O

= =

占个楼先

ORZ陶陶神牛

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

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

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

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