链接：https://www.luogu.org/problemnew/show/P3698

题目描述

小 Q 正在设计一种棋类游戏。

在小 Q 设计的游戏中，棋子可以放在棋盘上的格点中。某些格点之间有连线，棋子只能在有连线的格点之间移动。整个棋盘上共有 V 个格点，编号为0,1,2 … , V− 1，它们是连通的，也就是说棋子从任意格点出发，总能到达所有的格点。小 Q 在设计棋盘时，还保证棋子从一个格点移动到另外任一格点的路径是唯一的。

小 Q 现在想知道，当棋子从格点 0 出发，移动 N 步最多能经过多少格点。格点可以重复经过多次，但不重复计数。

输入输出格式

输入格式：

 

第一行包含2个正整数V, N，其中 V 表示格点总数，N 表示移动步数。

接下来V − 1行，每行两个数ai​,bi​ ，表示编号为 ai​,bi​ 的两个格点之间有连线。

 

输出格式：

 

输出一行一个整数，表示最多经过的格点数量。

 

输入输出样例

输入样例#1： 

5 21 02 13 24 3

输出样例#1： 

3

输入样例#2： 

9 50 10 22 64 28 11 33 73 5

输出样例#2： 

5

说明

【输入输出样例 1 说明】

从格点 0 出发移动 2 步。经过 0, 1, 2 这 3 个格点。

【输入输出样例 2 说明】

一种可行的移动路径为 0 → 1 → 3 → 5 → 3 → 7，经过 0, 1, 3, 5, 7 这 5 个格点。

【数据规模与约定】

对于 100%的测试点，N,V ≤ 100, 0 ≤a_i,b_i< V

题解：贪心，我们肯定最后走最长链，只走一次，不然他返回的步数很多，而走其他的点都必须要2歩，一步出去一步回来，所以我们只需要判断一下

(totstep - maxdep) / 2 和 (v  - maxdep) 的大小就好了

#include
      
       using namespace std;const int M = 200005;int dep[M], tmp[M], h[M], tot;struct edge{
    int v, nxt;}G[M];void add(int u, int v){G[++tot].v = v; G[tot].nxt = h[u]; h[u] = tot;}void dfs(int u, int f){    dep[u] = dep[f] + 1;    int child = 0;    for(int i = h[u]; i; i = G[i].nxt){        int v = G[i].v;        if(v == f)continue;        child++;        dfs(v, u);        if(tmp[u] < tmp[v])tmp[u] = tmp[v];    }    if(!child)tmp[u] = dep[u];}int main(){    int v, n, u, w;    scanf("%d%d", &v, &n);    for(int i = 1; i < v; i++){        scanf("%d%d", &u, &w);        add(u, w); add(w, u);    }    dfs(0, v+1);    if(n < tmp[1]){        printf("%d\n", n + 1);        return 0;    }    n -= tmp[0];    v -= tmp[0];    if((n + 1)/2 >= v)printf("%d\n", v + tmp[0]);    else printf("%d\n", (n + 1)/2 + tmp[0]);}