@[KANO07](/user/1048327)
```
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
vector<int>edge[65];
int cost[65], val[65];
int dp[65][40005];
int m,n;
void dfs(int u){
for(int v : edge[u]){
dfs(v);
for(int j = n; j >= 0; j--){ //父树内存
for(int k = j; k >= cost[v]; k--){ //子树内存
dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k - cost[v]] + val[v]);
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin>>n>>m;
n /= 10;
edge[0].clear();
for(int i = 1; i <= m; i++){
edge[i].clear();
int c,v,k;
cin>>c>>v>>k;
cost[i] = c/10;
val[i] = v*c;
edge[k].emplace_back(i);
}
dfs(0);
cout<<dp[0][n]<<"\n";
return 0;
}
by QuQ_ @ 2024-02-22 21:23:52
@[KANO07](/user/1048327) TLE解决了，但是~~WA~~
by QuQ_ @ 2024-02-22 21:24:09
@[KANO07](/user/1048327) #11WA了，建议打表
by QuQ_ @ 2024-02-22 21:24:52
@[KANO07](/user/1048327) 好吧不开O2还是TLE
by QuQ_ @ 2024-02-22 21:26:39
这是我受启发写的树形dp能AC
```cpp
#include <iostream>
#include <vector>
using namespace std;
typedef int ll;
ll n,m,f[61][100001];
ll v,p,q;
vector<ll> vec[101];
struct node{
ll pri,val;
}a[101];
void dfs(ll s){
for(int i=0;i<vec[s].size();i++){
ll k=vec[s][i];
dfs(k);
for(int j=n;j>=0;j--){
for(int l=j;l>=a[k].pri;l--){
f[s][j]=max(f[s][j],f[s][j-l]+f[k][l-a[k].pri]+a[k].val);
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
n/=10;
for(int i=1;i<=m;i++){
cin>>v>>p>>q;
a[i].pri=v/10;
a[i].val=v*p;
vec[q].push_back(i);
}
dfs(0);
cout<<f[0][n];
return 0;
}
```
by Fu_Tao @ 2024-03-13 21:15:26