题意：

给你n个物品，给出\(a_i\),\(b_i\)，分表代表选择第i个物品前必须先选择第\(a_i\)个物品和选择第i个物品后获得的收益，你可以选择m个物品，求收益最大值。

题解：

首先这题很像一个背包，即有依赖关系的背包。

对于这个问题我们可以用树形dp来做。

转化模型：将所有物品与其父亲连边，代表选择父亲后才能选择儿子，没有父亲的物品与一个虚拟结点0连边。

于是我们dfs做一遍树形背包，转移为：\(dp[u][j]=max(dp[u][j],dp[v][k]+dp[u][j-k])\)。

优化：做树形背包有一个很常见的优化是k每次只枚到儿子的siz，这样的总复杂度是\(O(n^2)\)。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define ll long long#define N 210using namespace std;int e_num;int h[N],nxt[N],to[N],val[N],dp[N][N];int gi() { int x=0,o=1; char ch=getchar(); while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar(); if(ch=='-') o=-1,ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return o*x;}void add(int x, int y) { nxt[++e_num]=h[x],to[e_num]=y,h[x]=e_num;} int dfs(int u, int m) { dp[u][1]=val[u]; int sizv=0,sizu=1; for(int i=h[u]; i; i=nxt[i]) { int v=to[i]; sizv=dfs(v,m-1); for(int j=m; j>=1; j--) for(int k=1; k<=sizv && k