和Heroes Of Might And Magic 相似，题目的询问是dp的一个副产物。
距离是不好表示成状态的，但是可以换一个角度想，如果知道了从一个点向子树走k个结点的最短距离，
那么知道最短距离就可以回答走x距离能访问到的最大结点数量。
当访问了一棵子树，想要访问子树外的结点时，一定要先从子树的根结点出来。
状态可以定义为dp[u][k][?]，u表示根节点，k表示访问u的k个子结点，?的取值为0和1表示 不回到u 和 回到u。
不难想到转移过程:
dp[u][k][0] <- dp[u][a][1] + dp[v][b][0]
dp[u][k][1] <- dp[u][a][1] + dp[v][b][1]
k = a+b+1, v 是 u的子节点
边界为 dp[u][0][0] = dp[u][0][1]表示停留在u.
真正困难的是转移的顺序，必须保证重复走一个结点只算一次，
实际计算的时候我们只能一个一个的枚举v，对于枚举到v的结点数量b只能从没有考虑过v结点的状态转移。
把结点数量看出物品，v的结点数实际上是一组物品，不能同时选。
剩下和分组背包差不多。
#include<bits/stdc++.h> using namespace std; #define PS push const int maxn = 505; const int INF = 0x3f3f3f3f; int hd[maxn], nx[maxn], to[maxn], ec; void add(int u,int v) { to[ec] = v; nx[ec] = hd[u]; hd[u] = ec++; } int fa[maxn], dist[maxn], deg[maxn], sz[maxn]; int ks; int n; int dp[maxn][2][maxn]; int sol() { queue<int> q; for(int i = 0; i < n; i++){ if(!deg[i]) { q.PS(i); } } int u; while(q.size()){ u = q.front(); q.pop(); sz[u] = 1; dp[u][0][0] = dp[u][1][0] = 0; for(int i = hd[u]; ~i; i = nx[i]){ int v = to[i]; sz[u] += sz[v]; for(int k = sz[u]-sz[v]; k < sz[u]; k++) dp[u][0][k] = dp[u][1][k] = INF; for(int k = sz[u]-1; k > 0; k--){//从大到小枚举k 保证是上一组的状态转移过来 for(int a = min(sz[v],k)-1; a >= 0; a--){//先枚举k，然后枚举物品保证组内物品不会同时选到 int b = k-1-a; //知道dp[v][b][0] 和 dp[v][b][1] 以后新增加的路径 dp[u][0][k] = min(dp[u][0][k],min(dp[u][0][b]+dp[v][1][a]+dist[v],dp[u][1][b]+dp[v][0][a])+dist[v]); dp[u][1][k] = min(dp[u][1][k],dp[u][1][b]+dp[v][1][a]+dist[v]*2); } } } if(!--deg[fa[u]]) q.PS(fa[u]);//fa[root]虽然不确定,但是在0~500内且deg = 0 } return u; } //#define LOCAL int main() { #ifdef LOCAL freopen("in.txt","r",stdin); #endif while(scanf("%d",&n),n){ memset(deg,0,sizeof(deg)); memset(hd,-1,sizeof(hd)); ec = 0; for(int i = 1; i < n; i++){ int u,f,d; scanf("%d%d%d",&u,&f,&d); fa[u] = f; dist[u] = d; add(f,u); deg[f]++; } printf("Case %d:\n",++ks); int *ans = dp[sol()][0]; int Q; scanf("%d",&Q); while(Q--){ int x; scanf("%d",&x); printf("%d\n",upper_bound(ans,ans+n,x)-ans);//能走的最大子结点数+1 } } return 0; }
UVA Live Archive 4015 Cave （树形dp，分组背包）
原文：http://www.cnblogs.com/jerryRey/p/4856560.html