TLE4个点求调 (玄关

蒟蒻T了6 7 8 9 《求调

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
template <typename T>
inline void read(T&x){
    int w=0;x=0;
    char ch = getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') w=1;
        ch = getchar();
    }
    while(ch>='0'&&ch<='9'){
        x = (x<<1)+(x<<3)+(ch^48);
        ch = getchar();
    }
    if(w) x=-x;
}
template <typename T,typename...Args>
inline void read(T&t,Args&...args){
    read(t);read(args...);
}
const int N = 4e4;
int V,n;
int ans[70][N];
int to[N],nex[N],w[N],v[N];
int head[N],edge_num;
inline void add(int a,int b,int ww,int vv){

}
int vis[N];
inline void dfs(int now){
//  cout << now << endl;
    vis[now] = 1;
    for(int i=head[now];i!=-1;i=nex[i]){
        int tto = to[i];
        if(vis[tto]) continue;
        vis[tto] = 1;
        dfs(tto);
        for(int j=V-w[now];j>=0;--j){
            for(int k=0;k<=j;++k){
                if(ans[now][j]<ans[now][j-k]+ans[tto][k]) ans[now][j]=ans[now][j-k]+ans[tto][k];
            }
        }
    }
    for(int i=V;i>=0;--i){
        if(i<w[now]) ans[now][i] = 0;
        else ans[now][i] = ans[now][i-w[now]]+v[now];
    }
}
int main(){
    read(V,n);
    memset(head,-1,sizeof(head));
    for(int i=1,vv,q;i<=n;++i){
        read(w[i],vv,q);
        to[++edge_num] = i;
        nex[edge_num] = head[q];
        head[q] = edge_num;
        v[i] = vv*w[i]/10;
    }
    dfs(0);
    printf("%d",ans[0][V]*10);
    return 0;
}