原题为HDU1561 The more，The better
Problem Description
ACboy很喜欢玩一种战略游戏，在一个地图上，有N座城堡，每座城堡都有一定的宝物，在每次游戏中ACboy允许攻克M个城堡并获得里面的宝物。但由于地理位置原因，有些城堡不能直接攻克，要攻克这些城堡必须先攻克其他某一个特定的城堡。你能帮ACboy算出要获得尽量多的宝物应该攻克哪M个城堡吗？
Input
每个测试实例首先包括2个整数，N,M.(1 <= M <= N <= 200);在接下来的N行里，每行包括2个整数，a,b. 在第 i 行，a 代表要攻克第 i 个城堡必须先攻克第 a 个城堡，如果 a = 0 则代表可以直接攻克第 i 个城堡。b 代表第 i 个城堡的宝物数量, b >= 0。当N = 0, M = 0输入结束。
Output
对于每个测试实例，输出一个整数，代表ACboy攻克M个城堡所获得的最多宝物的数量。
Sample Input
3 2
0 1
0 2
0 3
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2
0 0
Sample Output
5
13
这道题有两种算法，第一种算法是O（nw^2）的，就是直接在树上dp，之后枚举每一个节点，枚举每一个节点取得最大体积和当前取得的体积，就可以。
不过我们今天来说一下O(nw)的算法，因为普通的背包是可以线性解题的，这样才能达到二维的时间复杂度，那么我们怎么把一棵树转化为线性问题求解呢？
我们可以先求这棵树的dfs序，之后记录每一个点的子树大小，之后像正常dp一样讨论取或不取即可。
if(j+1<=m) dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j]+w[seq[i]]); dp[i+size[seq[i]]][j] = max(dp[i+size[seq[i]]][j],dp[i][j]);
第一行是取，第二行是不取，其中dp[i][j]表示在dfs序中到第i个节点已经用了j个体积所能获得的最大价值。因为这道题攻陷每个城堡所用的消耗固定为1，所以直接+1就可以。
不过这题并不是直接照抄dp转移方程就可以！这里有好多需要注意的事情。
第一个，我们在树形dp转化为线性问题的时候，要注意一个状态是不可以凭空生成的，也就是说我们不能在没有取父节点的情况下直接选取子节点，这会对第一行代码产生极大的影响，所以我们开一个vis数组以记录这种状态是否被取过，如果被取过的话我们就可以继续dp，否则不可以。
第二个，注意子树大小是怎么计算的……他是算自己的。所以我们递归的时候应该先把每个节点初始化为1，之后（我用的是链前）直接把其所有子节点的子树大小加起来就可以了。
第三个是dfs序的问题，这里一定要注意i表示dfs序中到第i个点，所以dfs序从0还是1开始存将会有至关重要的影响。在代码里我是从1开始存并从1开始dp，所以最后我们只要去dp[tot][m]就可以，其他情况需要视情况而定，如果实在不行的话自己打表分析一下。
这样就可以过了……要注意的东西挺多的，而且HDU不提供数据点debug很难受……
最后上代码。
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<queue> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') #define M 2005 using namespace std; typedef long long ll; const int INF = 2147483647; struct node { int next,to; }edge[M]; int n,dp[M][M],head[M],size[M],cnt,tot,ans,m,seq[M],w[M]; bool vis1[M][M]; int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } void init() { memset(edge,0,sizeof(edge)); memset(head,0,sizeof(head)); memset(dp,0,sizeof(dp)); memset(size,0,sizeof(size)); memset(seq,0,sizeof(seq)); memset(w,0,sizeof(w)); memset(vis1, 0, sizeof(vis1)); cnt = 0,tot = 0; } void add(int x,int y) { edge[++cnt].next = head[x]; edge[cnt].to = y; head[x] = cnt; } void build() { rep(i,1,n) { int x = read(); int y = read(); add(x,i); w[i] = y; } } void dfs(int x) { seq[tot++] = x; size[x] = 1; for(int i = head[x];i;i = edge[i].next) { int v = edge[i].to; dfs(v); size[x] += size[v]; } } void DP() { vis1[1][0] = 1; rep(i,1,tot + 1) rep(j,0,n) { if(vis1[i][j]) { if(j+1<=m) dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j]+w[seq[i]]); dp[i+size[seq[i]]][j] = max(dp[i+size[seq[i]]][j],dp[i][j]); vis1[i+1][j+1] = vis1[i+size[seq[i]]][j] = 1; } } } int main() { while(1) { n = read(),m = read(); if(!n && !m) break; init(); build(); dfs(0); DP(); printf("%d ",dp[tot][m]); } return 0; }