给一棵树，边上有权值，然后给一个权值x，问从根结点出发， 走不超过x的距离，最多能经过多少个结点。
走过的点可以重复走，所以可以从一个分支走下去，然后走回来，然后再走另一个分支
dp[u][j][0] 表示从u出发，走了j个点，然后不回到u点的最小花费
dp[u][j][1] 表示从u出发，走了j个点，然后回到u点的最小花费
dp[u][j][0] = min(dp[u][j][0], dp[v][k][0]+dp[u][j-k][1]+dis, dp[v][k][1]+dp[u][j-k][0]+2*dis);
可能是当前这个分支不回到u点，那么就是dp[v][k][0] + dp[u][j-k][1] +dis
可能是当前这个分支回到u点(那么u->v的边走两次，那么就是2*dis)，但是以前的分支不回到u点，dp[v][k][1] + dp[u][j-k][0] + 2*dis
dp[u][j][1] = min(dp[u][j][1], dp[v][k][1]+ dp[u][j-k][1] + dis)
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <math.h>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <bitset>
#include <algorithm>
#include <iostream>
#include <string>
#include <functional>
const int INF = << ; /* 树形背包
*/
const int N = + ;
struct Edge
{
int to, dis, next;
}g[N*];
int head[N], e, fa[N];
int dp[N][N][];
int size[N];
int n, u, v, dis, query[];
void addEdge(int u, int v, int dis)
{
g[e].to = v;
g[e].dis = dis;
g[e].next = head[u];
head[u] = e++;
}
void init()
{
memset(dp, 0x7f7f7f7f, sizeof(dp));
memset(head, -, sizeof(head));
memset(fa, -, sizeof(fa));
e = ;
}
void dfs(int u, int fa)
{
dp[u][][] = dp[u][][] = ;
size[u] = ;
for (int i = head[u];i != -;i = g[i].next)
{
int v = g[i].to;
if (v == fa) continue;
dfs(v, u);
size[u] += size[v];
for (int j = size[u];j >= ;--j)
for (int k = ;k <= size[v]; ++k)
{
dp[u][j][] = std::min(dp[u][j][], std::min(dp[u][j-k][]+dp[v][k][] + g[i].dis, dp[u][j-k][]+dp[v][k][] + g[i].dis * ));
dp[u][j][] = std::min(dp[u][j][], dp[u][j-k][] + dp[v][k][] + g[i].dis * );
} }
}
int main()
{
int tcase = ;
while (scanf("%d", &n) ,n)
{
init();
for (int i = ;i < n;++i)
{
scanf("%d%d%d", &u, &v, &dis);
addEdge(v, u, dis);
fa[u] = v;
}
int root;
for (int i = ;i < n;++i)
if (fa[i] == -)
root = i;
int q, x;
dfs(root, -);
scanf("%d", &q);
printf("Case %d:\n", tcase++);
while (q--)
{
int ans;
scanf("%d", &x);
for (int i = ;i <= n;++i)
if (dp[root][i][] <= x || dp[root][i][] <= x)
ans = i;
printf("%d\n", ans);
}
}
return ;
}