UVALive 4015 Caves--树形dp

原题链接：​​http://vjudge.net/problem/UVALive-4015​​

题意：n个部落，编号0到n-1，n-1条路连接n个部落，连成一棵树，机器人从树根出发，问在最多走x米最多经过多少部落。

分析：

dp[ i ][ j ][ 0 ]表示从i部落出发，经过j个部落且不回到起点 i 的最小路径；

dp[ i ][ j ][ 1 ]表示从i部落出发，经过j个部落且回到起点 i 的最小路径。

#define _CRT_SECURE_NO_DEPRECATE 

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<string>
#include<stdio.h>
#define INF 99999999
#define eps 0.0001
using namespace std;

int n, q;
int dp[505][505][2];
int son[505];
int cnt[505];
vector<int> vec[505];

void tree_dp(int u)
{
  for (int i = 1; i <= n; i++)
    dp[u][i][0] = dp[u][i][1] = INF;
  son[u] = 1;
  dp[u][1][0] = dp[u][1][1] = 0;
  for (int i = 0; i < vec[u].size(); i = i + 2)
  {
    int v = vec[u][i];
    int d = vec[u][i + 1];
    tree_dp(v);
    son[u] += son[v];
    for (int j = son[u]; j >= 2; j--)
      for (int k = 1; k <= min(j - 1, son[v]); k++)
      {
        dp[u][j][0] = min(dp[u][j][0], min(dp[u][j - k][0] + dp[v][k][1] + 2 * d, dp[u][j - k][1] + dp[v][k][0] + d));
        dp[u][j][1] = min(dp[u][j][1], dp[u][j - k][1] + dp[v][k][1] + 2 * d);
      }
  }
}

int main() 
{
  int T = 1;
  while (~scanf("%d", &n) && n)
  {
    memset(cnt, 0, sizeof(cnt));
    memset(son, 0, sizeof(son));
    for (int i = 0; i < n; i++)
      vec[i].clear();

    int x, y, z;
    for (int i = 1; i < n; i++)
    {
      scanf("%d%d%d", &x, &y, &z);
      vec[y].push_back(x);
      vec[y].push_back(z);
      cnt[x]++;
    }
    
    int root = 0;
    for (int i = 0; i < n;i++)
      if (cnt[i] == 0)
      {
        root = i;
        break;
      }
    tree_dp(root);

    scanf("%d", &q);
    printf("Case %d:\n", T++);
    while (q--)
    {
      scanf("%d", &x);
      int ans = 1;
      for (int i = 1; i <= n; i++)
        if (dp[root][i][0] <= x)
          ans = i;
      printf("%d\n", ans);
    }
  }
  return 0;
}