题目链接：https://vjudge.net/contest/164840#problem/D

题意： 给一棵树，每条边上有一些权值，求 长度不超过 x ，最多能走多少个点；

 

分析：

考虑每一个节点，他可以一直走下去，也可以走回来而走到他的兄弟节点；

 

状态定义： 

d[x][j][0/1] 从 i 出发，走 j 个节点的最短距离；

1、回来，这就是一个背包，更新当前节点；

2、不回来，则是要考虑从哪个部分不回来；

1 #include 
      
        2  3 using namespace std; 4  5 int n; 6 const int maxn = 550; 7 const int inf = 0x3f3f3f3f; 8 vector 
       
         g[maxn]; 9 int cnt[maxn];10 int son[maxn];11 12 int d[maxn][maxn][2];13 14 void dfs(int x) {15 16     for(int i=1; i<=n; i++)17         d[x][i][0] = d[x][i][1] = inf;18     d[x][1][0] = d[x][1][1] = 0;19 20 21     son[x] = 1;22     for(int i=0; i
        
         0; j--) {   ///这一重 相当于前面几个背包28             for(int k=1; k<=son[y]; k++) {  ///这一重 相当于当前这个背包中拿物品29                 d[x][j+k][1] = min(d[x][j+k][1],d[x][j][1]+d[y][k][1]+len*2);30                 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));31             }32         }33 34         son[x] +=son[y];35     }36 }37 38 int main() {39     int cas = 1;40     while(scanf("%d",&n),n) {41         for(int i=0; i<=n; i++)42             g[i].clear();43 44         memset(cnt,0,sizeof(cnt));45         for(int i=0; i
        
       
      

 

膜拜猫奴大牛；