讨论 / PID30 [By WSH]
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;

}

查看更多回复
提交回复