tjut 3593

#include<cstdio> #include<algorithm> #define MAX 100005 using namespace std; bool leaf[MAX]; int dp[505][10005];//非叶子节点最多500个 int G; int cost[MAX],val[MAX]; struct node{ int to,nxt; }edg[MAX]; int head[MAX]; int ind=0; void dfs(int now,int lim) { int v; for (int i = head[now]; i != -1; i = edg[i].nxt) { v = edg[i].to; if(leaf[v]) {//叶子节点 for (int j = lim; j >= cost[v]; j--) {//对叶子结点做01背包，更新父节点 dp[now][j] = max(dp[now][j-cost[v]]+val[v],dp[now][j]); } }else{//非叶子节点 if(lim >= cost[v]){ for (int j = lim-cost[v]; j >=0 ; j--) {//强制将子节点v放入父节点的泛化背包中，因为若想取子节点v的子节点，题目要求要先取v才行，这样才能更新子节点的值。 dp[v][j] = dp[now][j]+val[v]; } dfs(v,lim-cost[v]);//对儿子节点做背包。 for (int k = cost[v]; k <= lim; k++)//合并，更新父亲结点 dp[now][k] = max(dp[v][k-cost[v]],dp[now][k]); } } } } void addedge(int u,int v) { edg[ind].to = v; edg[ind].nxt = head[u]; head[u] = ind++; } int main() { int n; while(~scanf("%d %d",&n,&G)) { ind=0; memset(dp[0],0,sizeof(dp));//把零号节点初始化为0。 memset(head,-1,sizeof(head)); memset(leaf,1,sizeof(leaf)); cost[0] = 0; int fi; for (int i = 1; i <= n; i++) { scanf("%d %d %d",&cost[i],&val[i],&fi); if(fi == i) fi = 0; //加上0号节点，原图就由森林变成了树，便于处理。 addedge(fi,i); leaf[fi] = 0; } dfs(0,G); //从根节点开始递归。 printf("%d\n",dp[0][G]); } return 0; }