Analysis
我们发现如果忽略主从关系，那这道题就是一个裸的 01 背包问题。
主从关系处理也非常简单，借鉴 P2014 选课 的经验，转换成树上背包问题。
同理，本题是一个森林，若将 0 号节点参与建树的话就可以把森林转换成树，处理方便。
具体地，设 \(f_{i,j}\) 表示以 \(i\) 为父节点，剩余价钱（这里看作重量）为 \(j\) 时的最大价值。显然我们需要预处理出价值 = 重要度 \(\times\) 价钱。
树上背包具体实现的时候需要先处理子节点。
Code
/*
有依赖关系的dp统一用树上背包处理。
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 40000;
int n,m;
int f[200][N];
int w[N],v[N];
vector <int> Edge[N];
void dp(int noww,int t,int fa) //树上背包类似于记搜
{
if(t <= 0) return; //这个参数是必须的!和选课不同
for(int i=0;i<Edge[noww].size();i++)
{
int vv = Edge[noww][i];
if(vv == fa) continue; //不能回去
for(int j=n-w[vv];j>=0;j--) f[vv][j] = f[noww][j] + v[vv]; //只有先取now才能取用vv，先后顺序需要注意。题目保证一个儿子只对应一个父亲。
dp(vv,t-w[vv],noww); // 先搜儿子，树上dp板子
for(int j = n;j >= w[vv];j--) // 01背包倒着搜
{
f[noww][j] = max(f[noww][j],f[vv][j-w[vv]]); //我们已经预处理完了，直接取即可
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int v1,p,q;
cin>>v1>>p>>q;
Edge[q].push_back(i); //双向建边
Edge[i].push_back(q);
v[i] = v1*p; //预处理每件物品的价值
w[i] = v1;
}
m++;
dp(0,n,0); //虚拟节点参与，变森林为树qwq（和选课类似）
int maxn = 0;
for(int i=0;i<=n;i++)
{
maxn = max(maxn,f[0][i]); //f 数组第一维存的是剩余重量，所以需要是0.至于第二维我们显然不知道以哪个节点为fa的时候价值最大，取max即可。
}
cout<<maxn<<endl;
return 0;
}