E76 树上背包 P1064 [NOIP2006 提高组] 金明的预算方案

标程：

#include<bits/stdc++.h>
using namespace std;
const int N=65, M=3.2e4+10;
int n, m, pool[N*M], w[N], v[N], siz[N], rdfn[N], id;
vector<int>f[N], G[N];
void dfs(int x)
{
    siz[x]=1;
    for(auto y:G[x]) dfs(y), siz[x] += siz[y];
    rdfn[++id]=x;
}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);
    cin>>m>>n;
    int (&f)[n+2][m+1]=decltype(f)(pool);
    for(int i=1, x;i<=n;++i) cin>>w[i]>>v[i]>>x, v[i]*=w[i], G[x].push_back(i);
    id=0;dfs(0);
    for(int i=1;i<=id;++i)
	{
        int x=rdfn[i];
        for(int j=0;j<=m;++j)
		{
            f[i][j]=f[i-siz[x]][j];//秒 
            if(j>=w[x]) f[i][j]=max(f[i][j], f[i-1][j-w[x]]+v[x]);
        }
    }
    cout<<f[id][m]<<'\n';
    //cerr<<"Running Time: "<<(double)clock()/CLOCKS_PER_SEC<<" s\n";
    return 0;
}