题意：一棵n个节点的有根树，树的边有正整数权，表示两个节点之间的距离，你的任务是回答这样的询问，从根节点出发，走不超过x单位的距离，最多能走多少个节点，节点经过多次算一个，对于每次的询问输出：经过节点数最大的值
思路：树形DP，因为最近做的树形DP，都是三维的，最后一维表示是与否的，所以
用d[i][j][c]表示以i为根节点的树经过了j个节点，1代表不返回i，0返回i，的最短距离
所以我们单独考虑一棵树，根节点是i，起先假设它的son[i] = 1，那么初始话就是d[i][1][0]=d[i][1][1] = 0,接下来就是单独考虑它的子节点了，首先考虑如果返回的话，就一种可能就是：它走其他的子树要返回，然后还要对当前的节点要返回；如果不返回的话，那么它可能走其他的子树要返回，当前的不返回，还有就是当前的子树返回，其他的子树不返回
#include#include #include #include #include using namespace std; const int MAXN = 550; int d[MAXN][MAXN][2]; int n,son[MAXN],cnt[MAXN]; vector g[MAXN]; void dfs(int x){ for (int i = 1; i <= n; i++) d[x][i][0] = d[x][i][1] = 0x3f3f3f3f; d[x][1][0] = d[x][1][1] = 0; son[x] = 1; for (int i = 0; i < g[x].size(); i += 2){ int y = g[x][i],len = g[x][i+1]; dfs(y); for (int j = son[x]; j > 0; j--){ for (int k = 1; k <= son[y]; k++){ d[x][j+k][1] = min(d[x][j+k][1],d[x][j][1]+d[y][k][1]+len*2); d[x][j+k][0] = min(d[x][j+k][0],min(d[x][j][0]+d[y][k][1]+len*2,d[x][j][1]+d[y][k][0]+len)); } } son[x] += son[y]; } } int main(){ int cas = 1; while (scanf("%d",&n) != EOF && n){ for (int i = 0; i <= n; i++) g[i].clear(); memset(cnt,0,sizeof(cnt)); for (int i = 1; i < n; i++){ int u,v,w; scanf("%d %d %d",&u,&v,&w); cnt[u]++; g[v].push_back(u); g[v].push_back(w); } int root = 0; for (int i = 1; i < n; i++) if (!cnt[i]) root = i; dfs(root); int q,x; scanf("%d",&q); printf("Case %d:\n",cas++); while (q--){ scanf("%d",&x); int ans = 1; for (int i = 1; i <= n; i++) if (d[root][i][0] <= x) ans = i; printf("%d\n",ans); } } return 0; }