Uva(1407)(Caves)

链接：https://vjudge.net/problem/UVA-1407
思路：树形dp，以前做过子节点与父节点有联系那种，而这种求最多多少个点的根本不会设计状态，看了题解，用dp[u][j][0/1]表示从u开始走j个节点需要走的最短距离，0/1表示最后在u点或者不在u点。首先为什么dp数组不保存点的个数呢，这样的话避免不了要判重，即哪些点走过，哪些没有。但这个图是无向图，且可以走回父节点，所以很难去设计判重的方法，而只好转换为距离最小值，然后比较与询问的q，找到比q的距离小中最大的那个对应的j就是答案，状态转移的话，如果最后在u的话，则沿途所有的边都要走两次，只有一种状态转移，如果不在的话则要考虑两种情况，一种是走其他子树回了u点，这一个子树可以不用回，另一种是这个子树要回，其他子树可以不用回= =
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 510;
int dp[maxn][maxn][2],d[maxn],tot[maxn],n;
vector<int> G[maxn];

void dfs(int u){
    tot[u] = 1;
    for(int i=0;i<G[u].size();i++){
        int v = G[u][i];
        dfs(v);
        tot[u]+=tot[v];
    }
    dp[u][1][0] = dp[u][1][1] = 0;
    for(int i=2;i<=tot[u];i++){
        dp[u][i][0] = dp[u][i][1] = 1e9;
    }
    for(int i=0;i<G[u].size();i++){
        int v = G[u][i];
        for(int j=tot[u];j>=2;j--){//枚举下u下一共多少个节点，2是因为包括u，v在内
            for(int k=1;k<=tot[v];k++){//枚举走v一下走了多少个节点，从1开始是因为v已经在内
                dp[u][j][0] = min(dp[u][j][0],dp[u][j-k][0]+dp[v][k][0]+2*d[v]);
                dp[u][j][1] = min(dp[u][j][1],dp[u][j-k][0]+dp[v][k][1]+d[v]);
                dp[u][j][1] = min(dp[u][j][1],dp[u][j-k][1]+dp[v][k][0]+2*d[v]);
            }
        }
    }
}

int main(){
    int kase = 0;
    while(scanf("%d",&n)&&n){
        for(int i=0;i<=n;i++)G[i].clear();
        memset(tot,0,sizeof(tot));
        memset(dp,0,sizeof(dp));
        memset(d,0,sizeof(d));
        for(int i=1;i<=n-1;i++){
            int u,v,w;
            scanf("%d%d%d",&v,&u,&w);
            G[u].push_back(v);//做成有向图是为了方便防止父子节点来回走
            d[v] = w;
        }
        dfs(0);
        int q;
        scanf("%d",&q);
        printf("Case %d:\n",++kase);
        while(q--){
            int k;
            scanf("%d",&k);
        int ans = 0;
        for(int i=n;i>=1;i--){
            if(k>=dp[0][i][1])
            {
                ans = i;
                break;
            }
        }
        printf("%d\n",ans);
        }
    }
    return 0;
}