Wushanghong 2017-09-09 23:54:40
点我顶贴
收藏
删除
#include<cstdio>
#include<cstring>
int n,m;
int f[1010][110];
struct node{int lc,rc,c;} tr[1110];
void mt()
{
for(int i=1;i<=n;i++)
{
scanf("%d",&tr[i].c);
}
for(int i=1;i<=n;i++)
{
int fa,x;
scanf("%d %d",&fa,&x);
tr[x].rc=tr[fa].lc;
tr[fa].lc=x;
}
}
int maxx(int x,int y){ return x>y?x:y; }
void dfs(int x,int y)
{
if(f[x][y]>=0) return;
if(x==0 || y==0) { f[x][y]=0; return ; }
dfs(tr[x].rc,y);
f[x][y]=maxx(f[x][y],f[tr[x].rc][y]);
for(int i=0;i<y;i++)
{
dfs(tr[x].rc,i);
dfs(tr[x].lc,y-i-1);
f[x][y]=maxx(f[x][y],f[tr[x].rc][i]+f[tr[x].lc][y-i-1]+tr[x].c);
}
}
int main()
{
memset(f,-1,sizeof(f));
scanf("%d %d",&n,&m);
mt();
dfs(tr[0].lc,m);
printf("%d",f[tr[0].lc][m]);
return 0;
}