枞阳网站制作,百家号网站开发属于什么领域,小程序助手app下载,濮阳网站建设电话正题 题目大意
一棵树每个点有权值#xff0c;选择kkk个点#xff0c;要求选子节点之前必须要选父节点。求最大权值。 解题思路
树形背包限制一下必须选kkk个就好了 codecodecode
#includecstdio
#includealgorithm
#includecstring
#define N 11…正题 题目大意
一棵树每个点有权值选择kkk个点要求选子节点之前必须要选父节点。求最大权值。 解题思路
树形背包限制一下必须选kkk个就好了 codecodecode
#includecstdio
#includealgorithm
#includecstring
#define N 110
using namespace std;
struct node{int to,next;
}a[N];
int n,k,tot,ls[N],f[N][N],w[N];
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;
}
void dp(int x){if(x!1) f[x][1]w[x];else f[x][0]0;for(int lls[x];l;la[l].next){int ya[l].to;dp(y);for(int ik;i1;i--)for(int j1;jk;j)if(i-j0) break;else f[x][i]max(f[x][i],f[x][i-j]f[y][j]);}return;
}
int main(){memset(f,0xcf,sizeof(f));scanf(%d%d,n,k);for(int i2;in;i)scanf(%d,w[i]);for(int i1;in;i){int x,y;scanf(%d%d,x,y);if(x) addl(i,x);if(y) addl(i,y);}dp(1);printf(%d,f[1][k]);
}
