题目大意：给定一棵 N 个节点的有根树，1 号节点为根节点，叶子节点有点权，每条边有边权，每经过一条边都减去该边权，每经过一个节点都加上该点权，求在保证权值和为非负数的前提下最多能经过多少个叶子节点。
题解：(dp[u][i]) 表示在以 u 为根节点的子树中，经过 i 个叶子节点的最大权值和，则有状态转移方程：$$dp[u][i]=max(dp[u][i],dp[v][k]+dp[u][i-k])$$。
一般前提为第一要素，作为要最优化的值，将要求的最优化的值最为附加属性，最后在满足前提的条件下遍历附加属性求出答案。
update on 2019.5.24
学习到了树上背包问题的上下界优化。
一开始做这道题肯定会觉得复杂度分析很奇怪，即：三个 for 循环竟然过了3000的数据量。
最后看了大佬的博客终于明白了，复杂度从严格意义上来说就是 (O(n^2)) 的。
感性证明如下：
我们实现的 dfs 过程可以看作是子树维护的信息合并的过程。在这个过程中，发现任意两个点为根节点的子树信息均发生且仅发生了一次合并。而对于任意两个点的信息合并仅发生在这两个节点的 lca 处，因此时间复杂度为 (O(n^2))。
稍微严谨一点的证明如下：
[T_u=sumlimits_{fa[v]=u}T_v+f(u)
]
首先证明对于子树合并的过程复杂度是 (O(sz[u]^2)) ：
[egin{aligned} f_{u} &=1+left(1+s i zleft[v_{1}
ight]
ight) imes operatorname{siz}left[v_{1}
ight]+left(1+operatorname{siz}left[v_{1}
ight]+s i zleft[v_{2}
ight]
ight) imes operatorname{siz}left[v_{2}
ight]+cdots+operatorname{siz}[u] imes operatorname{siz}left[v_{k}
ight] \ &le 1+sum_{faleft[v_{i}
ight]=u} operatorname{siz}left[v_{i}
ight] imes(operatorname{siz}[u]+1) \ &=O(operatorname{siz}[u]^{2}) end{aligned}
]
再证明前面子树的和式也是 (O(sz[u]^2))：
利用数学归纳法可知，每个子树都是 (O(sz[v]^2)) 的，那么在合并的过程中，利用均值不等式（平方的和大于和的平方）可直接证出。
因此，总的时间复杂度为 (O(n^2))。
代码如下
#include <bits/stdc++.h>
using namespace std;
const int maxn=3010;
struct node{
int nxt,to,w;
}e[maxn<<1];
int tot,head[maxn];
inline void add_edge(int from,int to,int w){
e[++tot]=node{head[from],to,w},head[from]=tot;
}
int n,m,val[maxn],dp[maxn][maxn];
void read_and_parse(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n-m;i++){
int k;scanf("%d",&k);
for(int j=1;j<=k;j++){
int to,w;scanf("%d%d",&to,&w);
add_edge(i,to,w);
}
}
for(int i=n-m+1;i<=n;i++)scanf("%d",&val[i]);
memset(dp,0xcf,sizeof(dp));
}
int dfs(int u){
dp[u][0]=0;
if(u>n-m){dp[u][1]=val[u];return 1;}
int sum=0;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
int t=dfs(v);sum+=t;
for(int j=sum;j;j--)
for(int k=1;k<=t;k++)
dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]-e[i].w);
}
return sum;
}
void solve(){
dfs(1);
int ans=0;
for(int i=m;i;i--)if(dp[1][i]>=0){ans=i;break;}
printf("%d
",ans);
}
int main(){
read_and_parse();
solve();
return 0;
}