[CQOI2017]小Q的棋盘

贪心

题面

一棵有$n$个结点的树，问从$1$（根）结点出发，走$m$步最多能经过多少结点。

• $n\leq100$

解析

数据范围亮了
显然，在根结点周围转一圈再回来，走最长链到底是最值的。
于是先求出最长链$L$。
如果$L>m$，$ans=m+1$;
否则剩下$n-(L-1)$步，能多走$\frac{n-L+1}{2}$个点。（画画图发现找不出什么特殊情况）
即

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define re register
#define il inline
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=1e4+100;
int n,m,h[N],cnt,L;
struct Edge{int to,nxt;}e[N<<1];
il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void dfs(re int u,re int fa,re int deep)
{
  L=max(deep,L);
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v==fa) continue;
      dfs(v,u,deep+1);
    }
}
int main()
{
  memset(h,-1,sizeof(h));
  n=gi();m=gi();
  fp(i,1,n-1)
    {
      re int u=gi()+1,v=gi()+1;
      add(u,v);add(v,u);
    }
  dfs(1,0,1);
  if(L>=m) printf("%d\n",m+1);
  else printf("%d\n",min(n,L+((m-L+1)>>1)));
  return 0;
}