Description：

给一棵树，问从根开始最多走 $k$ 步最多能经过多少不同的点。

$1\leqslant n\leqslant 100$

Solution：

树形 $DP$ 套路， $f[i][j]$ 表示从 $i$ 开始走 $j$ 步回到 $i$ 最多能经过几个点， $g[i][j]$ 表示不用回来， $f$ 只能由 $f$ 转移来， $g$ 能由 $g$ 和 $f$ 或者 $f$ 和 $g$ ，注意这一点，也就是说可以先走一个不回来的，后走一个不回来的，或者中间走一个，也就是说有两个转移。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 110

#define R register

inline int rd()

{

    R int res = 0,f = 1;

    R char c = getchar();

    while(!isdigit(c))

    {

        if(c == '-')f = -1;

        c = getchar();

    }

    while(isdigit(c))

    {

        res = (res << 1) + (res << 3) + c - '0';

        c = getchar();

    }

    return res * f;

}

struct edge

{

    int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

    ++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

    ++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;

    return;

}

bool v[MAXN];

int f[MAXN][MAXN],g[MAXN][MAXN];

void dp(int k)

{

    v[k] = true;

    for(int i = 0;i <= m;++i)f[k][i] = 1;

    for(int i = 0;i <= m;++i)g[k][i] = 1;

    for(int i = lin[k];i != 0;i = e[i].nxt)

    {

        if(v[e[i].to])continue;

        dp(e[i].to);

        for(int j = m;j >= 0;--j)

            for(int l = 0;l <= j - 2;++l)

                g[k][j] = max(g[k][j],g[k][l] + f[e[i].to][j - 2 - l]); 

        for(int j = m;j >= 0;--j)

            for(int l = 0;l <= j - 1;++l)

                g[k][j] = max(g[k][j],f[k][l] + g[e[i].to][j - 1 - l]);

        for(int j = m;j >= 0;--j)

            for(int l = 0;l <= j - 2;++l)

                f[k][j] = max(f[k][j],f[k][l] + f[e[i].to][j - 2 - l]);

    }

    return;

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i = 1;i < n;++i)add(rd() + 1,rd() + 1);

    dp(1);

    cout << g[1][m] << endl;

    return 0;

}