Apple Tree （POJ2486 _Apple

一身转战三千里，一剑曾当百万师。这篇文章主要讲述Apple Tree （POJ2486相关的知识，希望能为你提供帮助。
题目传送门　题解：第一道树上背包题qaq
【Apple Tree （POJ2486】考虑每个节点在最终答案中的类型：1，不经过；2，经过但不返回；3，经过且返回（返回的定义是最终的停止节点不位于该节点的子树中）
对于第一种类型的节点，不用考虑。
对于后两种类型，我们设f[i][j][0]表示在第i个节点的子树中走j步且最终回到i节点所能够获得的最大权值，f[i][j][1]表示最终不回到i节点获得的最大权值。
对于一个节点的每一个子节点，都要选择其中的一种状态。我们可以把该问题抽象成分组背包问题：一个容量为j的背包，有siz组物品（siz相当于子节点数目），每组物品只能选一种。那么我们可以得到状态转移方程：
f[i][j][0] = max{f[v][k][0]+f[i][j-k-2][0]} （既然要回到该节点，那么对于子节点v来说肯定也要回到v节点，且下去上来各一步，故多用掉两步）
f[i][j][1] = max{f[v][k][0]+f[i][j-k-2][1]} （对于v节点来说，下去不回来，那么其他的节点下去后就必须回来）
f[i][j][1] = max{f[v][k][1]+f[i][j-k-1][0]} （该节点回来，那么其他节点可以不回来）

1 #include< iostream> 2 #include< cstdio> 3 #include< cstring> 4 #define LL long long 5 #define RI register int 6 using namespace std; 7 const int INF = 0x7ffffff ; 8 const int N = 100 + 10 ; 9 const int K = 200 + 10 ; 10 11 inline int read() { 12int k = 0 , f = 1 ; char c = getchar() ; 13for( ; !isdigit(c) ; c = getchar()) 14if(c == ‘-‘) f = -1 ; 15for( ; isdigit(c) ; c = getchar()) 16k = k*10 + c-‘0‘ ; 17return k*f ; 18 } 19 20 struct Edge { 21int to, next ; 22 }e[N< < 1] ; 23 int n, k, cnt = 0 ; int head[N], w[N], f[N][K][2] ; // 0表示回来，1表示不回来 24 inline void add_edge(int x,int y) { 25e[++cnt].to = y, e[cnt].next = head[x], head[x] = cnt ; 26 } 27 28 void dfs(int x,int fa) { 29for(int j=0; j< =k; j++) f[x][j][0] = f[x][j][1] = w[x] ; 30for(int i=head[x]; i; i=e[i].next) { 31int y = e[i].to ; if(y == fa) continue ; 32dfs(y,x) ; 33for(int j=k; j> =0; j--) { 34for(int kk=0; kk< =j; kk++) { 35if(j > = kk+2) f[x][j][0] = max(f[x][j][0],f[x][j-kk-2][0]+f[y][kk][0]) ; 36if(j > = kk+2) f[x][j][1] = max(f[x][j][1],f[x][j-kk-2][1]+f[y][kk][0]) ; 37if(j > = kk+1) f[x][j][1] = max(f[x][j][1],f[x][j-kk-1][0]+f[y][kk][1]) ; 38} 39} 40} 41 } 42 43 int main() { 44while(~scanf("%d %d",& n,& k)) { 45cnt = 0 ; memset(head,0,sizeof(head)) ; 46for(int i=1; i< =n; i++) w[i] = read() ; 47for(int i=1; i< n; i++) { 48int x = read(), y = read() ; 49add_edge(x,y) ; add_edge(y,x) ; 50} 51dfs(1,0) ; 52printf("%d\n",max(f[1][k][0],f[1][k][1])) ; 53} 54return 0 ; 55 }

第一次就错在了子节点中只能有一个下去不回来qwq