dp 解法：

首先，如果做比较常规的状态设计（如 $f_{i,j}$ 表是走 $i$ 步结尾为 $j$ 时的最大方案数），会有一个非常明显的问题：从父结点（以 $0$ 为根）转移过来时，你没有办法判断之前是否已经走过这个点，很容易就会多加或少加。

既然父节点这么难考虑，我们直接不考虑了！设 $f_{i,j}$ 为在以 $i$ 为根的子树中走 $j$ 步最多能访问的点数，那么此时就又会出现一个问题：你子树的最优方案可能不会回到根，在多棵子树合并时极难处理。所以我们再单开一个 $g_{i,j}$ 表示为在以 $i$ 为根的子树中走 $j$ 步并回到根节点最多能访问的点数。

$g_{i,j}$ 好转移，直接枚举分到当前这颗子树的步数 $k$，显然这颗子树也要回根，所以每枚举一颗子树的根 $v$，就有：

$$g_{i,j}=\max_{k=0}^{k\le j-2}\{g_{i,j-k-2}+g_{v,k}\}$$

对于 $f_{i,j}$，不回根要分两种情况：在新的这颗子树中一去不返或留在在之前的子树中，对于前者，这要求你在枚举前面的子树中必须回根，对于后者，这要求你走完新的字数后必须回根。即：

$$f_{i,j}=\max_{k-0}^{k\le j-1}\{\max(g_{i,j-k-1}+f_{v,k},f_{i,j-k-2}+g_{v,j})\}$$

直接转移即可。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int dp[105][105];
int dp2[105][105];
vector<int> g[105];
void dfs(int d,int fa){
	dp[d][0]=dp2[d][0]=1;
	for(auto v:g[d]){
		if(v==fa){
			continue;
		}
		dfs(v,d);
		for(int i=m;i>=1;i--){
			for(int j=i;j>=0;j--){
				if(i-j-2>=0){
					dp[d][i]=max(dp[d][i],dp[d][i-j-2]+dp[v][j]);
				}
				if(i-j-1>=0){
					dp2[d][i]=max(dp2[d][i],dp[d][i-j-1]+dp2[v][j]);
				}
				if(i-j-2>=0){
					dp2[d][i]=max(dp2[d][i],dp2[d][i-j-2]+dp[v][j]);
				}
			}	
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		g[x+1].push_back(y+1);
		g[y+1].push_back(x+1);
	}
	dfs(1,0);
	int ans=0;
	for(int i=1;i<=m;i++){
		ans=max(ans,dp2[1][i]);
	}
	cout<<ans;
	return 0;
} 

贪心解法：

首先，在走时，我们肯定先考虑访问那些未经访问的节点，因为这样不走回头路就不会浪费步数。

那么在这么走到不能走之后，我们走过的路一定会构成一条从根到某个叶子节点的链，那么我们一定是先去走走上最长的那条连最赚。

那对于所有其他的点，如果我们还有剩下的步数，我们考虑在走最长路之前先消耗掉，那么此时，我们考察它与他的父节点之间这条边，显然只会被经过两次（下来一次，回根一次），毕竟如果要更多次地往上走来访问其他的子树，那为什么不先去搜完之后再来访问呢？

所以对于所有的其他点，我们只需要额外消耗两步就能访问到它。

答案就是 $\min(n,mx+(m-mx+1)/2)$（$mx$ 为最长链的长度）。

我是废物!全场就我不会做这道题......

我也就输出V骗了个50分

很明显这道题是贪心，尽量不重复走每一个点，说白了就是走最长链，所以我就就直接遍历一遍这颗树， 找出最长链的长度，然后和n进行比较：

1：n比最长链的长度小，那就是输出n+1，因为起点也算在内

2：n比最长链的长度大或者相同，那要分类讨论：

第一种情况是n步之内能走完整棵树那就输出V(我也没想到有一半的样例是这样的)

第二种情况是走不完整棵树，那就看走完这条在最长链后退回时，这条链上的点有没有连着别的没走的点，又因为题目保证每两点间有且只有一条路径，所以每退回一个点就有能再走一个新的点。

也就是现在每走两步就多访问一个点，这是走完最长链后的最优情况了，最终答案是$min(V,mx+(n-mx+1)/2)$(mx表示最长链的长度)

最后实现即可

#include<bits/stdc++.h>
using namespace std;
bool v[110];vector<int>G[110];
int h[110],cnt,n,V,mx;
void dfs(int x,int dep)
{
	v[x]=1;mx=max(mx,dep);
	for(int y:G[x])if(!v[y])dfs(y,dep+1);
}
int main()
{
	scanf("%d%d",&V,&n);
	for(int i=1,x,y;i<V;i++)
	{
		scanf("%d%d",&x,&y);
		G[x].push_back(y);G[y].push_back(x);
	}
	dfs(0,1);
	if(mx>n)printf("%d\n",n+1);
	else printf("%d\n",min(V,mx+((n-mx+1)/2)));
	return 0;
}

安利下自己的博客 题目链接

---

首先这是一颗树。

这一题我们用贪心的方法来解决，首先来看看样例：

样例1很不友好，不如不给，显然我们可以经过3个点。

我们可以从样例2发现我们的贪心策略。

为了实现经过的点最多的这一条件，我们希望每次走一步都多走一个点，如果我们选择最长链的话，在链上每走一步就多走了一个点，如果走不完最长链，那答案就是步数+1，而如果走完最长链还有剩余步数的话，每两步可以多访问一个节点。

为什么剩余步数每两步可以多访问一个节点？

对于没有全访问的情况（如果这种方法求出来的值大于总数，则输出总数），最长链上肯定存在一条边连着一个没有访问的节点 ，当走到这里的时候，可以花两步去访问再回来。

为什么最长链是最优的？

显然，因为如果我们不走最长链的话，我们走任意其他的链对答案的贡献都没有最长链大，虽然剩下的剩余步数多，但是根据上面的推论，每两个剩余步数才有一个贡献，因此最长链是最优的。

讲得已经比较清楚了，有些细节没有提到，建议先自己写一遍再看代码！！

代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 103;
int Nt[MAXN<<1],Head[MAXN<<1],to[MAXN<<1],tot;
bool used[MAXN];
int n,m;
int mx=0;

void add(int a,int b){
	Nt[++tot]=Head[a];
	to[tot]=b;
	Head[a]=tot;
}	

void dfs(int pos,int dep){//最长链可以用深搜跑最大深度得到
	used[pos]=1;
    mx=max(mx,dep);
	for(int i=Head[pos];i;i=Nt[i]){
		int y=to[i];
		if(used[y])continue;
		dfs(y,dep+1);
	}
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b);add(b,a);
	}
	dfs(0,1);
	if(m<=mx-1)printf("%d\n",m+1);//如果走不完最长链，那答案就是步数+1
	else printf("%d\n",min(n,mx+(m-mx+1)/2));
	return 0;
}

以零号节点为根的一颗树，求从根节点走$N$步，最多能经过多少节点。

从根节点出发访问$x$个节点需要走$x$步，如果要返回根节点则需要走$2x$步。

#include<bits/stdc++.h>
using namespace std;
const int N = 114;
vector<int> G[N];
int vis[N], d = 0;

void dfs(int x, int dep)
{
    d = max(d, dep);
    vis[x] = 1;
    for (auto y : G[x]) if (!vis[y])
        dfs(y, dep + 1);
}

int main()
{
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n - 1; i++)
    {
        int x, y; cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(0, 1);
    if (d >= m + 1) cout << m + 1;
    else cout << min(n, (m - d + 1) / 2 + d);
    return 0;
}