uva 1407(树形dp)

题意：有一个机器人从一个节点进入一棵树，给出n个节点之间的距离，如果机器人的能量为x，也就是最多走x，且机器人不需要回到起点，问机器人最多能走多少个节点。
题解：
f[i][j][0] : 遍历子树i的j个节点且最后不需要回到子树的根节点i最少用多少能量
f[i][j][1]：遍历子树i的j个节点且最后回到子树的根节点i最少用多少能量
首先要遍历出每个节点i有多少个子节点childnum[i]，然后针对每个子树中的子节点再枚举，状态转移方程，其中v是i的直接子节点：
f[i][j][0] = min{f[i][j][0], min{f[i][j-k][1]+f[v][k][0]+w, f[i][j-k][0]+f[v][k][1]+2*w}}
f[i][j][1] = min{f[i][j][1], f[i][j-k][1]+f[v][k][1]+2*w}
画图可以更好的理解这两个状态转移方程。

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 505;
const int INF = 0x3f3f3f3f;
int f[N][N][2], x, n, vis[N], childnum[N];
vector<int> g[N], len[N];

int dp(int u) {
    vis[u] = childnum[u] = 1;
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (!vis[v]) {
            childnum[u] += dp(v);
            vis[v] = 0;
        }
    }
    f[u][1][0] = f[u][1][1] = 0;
    for (int i = 0; i < g[u].size(); i++) {//枚举u的儿子节点
        int v = g[u][i], w = len[u][i];
        if (vis[v])
            continue;
        for (int j = childnum[u]; j >= 1; j--) //枚举在子树u中要遍历节点数量
            for (int k = 1; k <= childnum[v] && k < j; k++) { //枚举要遍历的u的儿子节点的子节点数量
                f[u][j][0] = min(f[u][j][0], min(f[u][j - k][1] + f[v][k][0] + w, f[u][j - k][0] + f[v][k][1] + 2 * w));
                f[u][j][1] = min(f[u][j][1], f[u][j - k][1] + f[v][k][1] + 2 * w);
            }
    }
    return childnum[u];
}

int main() {
    int cas = 1;
    while (scanf("%d", &n) == 1 && n) {
        memset(f, INF, sizeof(f));
        memset(vis, 0, sizeof(vis));
        for (int i = 0; i < n; i++) {
            g[i].clear();
            len[i].clear();
        }
        int que, v, u, d;
        for (int i = 0; i < n - 1; i++) {
            scanf("%d%d%d", &u, &v, &d);
            g[v].push_back(u);
            len[v].push_back(d);
        }
        dp(0);
        scanf("%d", &que);
        printf("Case %d:\n", cas++);
        while (que--) {
            scanf("%d", &x);
            for (int i = n; i >= 1; i--)
                if (f[0][i][0] <= x) {
                    printf("%d\n", i);
                    break;
                }
        }
    }
    return 0;
}