题面

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

• \(n\leq100\)

  解析

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

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #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;}