emmm感觉背包白学了，40分卡不动了/kk

code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <stdlib.h>
#include <stack>
#include <queue>
#define ri register int
#define N 100
#define M 1000005

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}

int son[N][5],w[N],v[N];
int cnt[N],fat[N];
int dp[M];

int main(){
    int m=read(),n=read();
    for(ri i=1;i<=n;i++){
    	int a=read(),b=read(),fa=read();
    	son[fa][++cnt[fa]]=i;
    	if(fa)fat[i]++;
    	w[i]=a*b,v[i]=a;
	} 
	for(ri i=1;i<=n;i++){
		if(!fat[i]){
			for(ri j=m;j>=v[i];j--){
				dp[j]=std::max(dp[j],dp[j-v[i]]+w[i]);
				if(j-(v[i]+v[son[i][1]])>=0)
				    dp[j]=std::max(dp[j],dp[j-v[i]-v[son[i][1]]]+w[i]+w[son[i][1]]);
				if(j-(v[i]+v[son[i][2]])>=0)
				    dp[j]=std::max(dp[j],dp[j-v[i]-v[son[i][2]]]+w[i]+w[son[i][2]]);
				if(j-(v[i]+v[son[i][2]]+v[son[i][1]])>=0)
				    dp[j]=std::max(dp[j],dp[j-v[i]-v[son[i][1]]-v[son[i][2]]]+w[i]+w[son[i][1]]+w[son[i][2]]);
			}
		}
	}
	printf("%d",dp[m]);
	return 0;
}