洛谷P3698 [CQOI2017]小Q的棋盘
考虑一个贪心，先在根节点周围转一圈，然后再往下走最长链肯定是最优的
然后设最长链的长度为$d$，如果$mleq d$，那么答案为$m+1$
否则的话还剩下$m-d+1$步，又得保证能走回来，所以答案为$min{n,d+frac{m-d+1}{2}}$
1 //minamoto 2 #include<iostream> 3 #include<cstdio> 4 using namespace std; 5 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 6 char buf[1<<21],*p1=buf,*p2=buf; 7 template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;} 8 int read(){ 9 #define num ch-'0' 10 char ch;bool flag=0;int res; 11 while(!isdigit(ch=getc())) 12 (ch=='-')&&(flag=true); 13 for(res=num;isdigit(ch=getc());res=res*10+num); 14 (flag)&&(res=-res); 15 #undef num 16 return res; 17 } 18 const int N=105; 19 int head[N],Next[N<<1],ver[N<<1],tot; 20 inline void add(int u,int v){ 21 ver[++tot]=v,Next[tot]=head[u],head[u]=tot; 22 } 23 int dep[N],n,m,res,d; 24 void dfs(int u,int fa){ 25 dep[u]=dep[fa]+1; 26 for(int i=head[u];i;i=Next[i]){ 27 int v=ver[i]; 28 if(v!=fa) dfs(v,u); 29 } 30 } 31 int main(){ 32 // freopen("testdata.in","r",stdin); 33 n=read(),m=read()+1; 34 for(int i=1,u,v;i<n;++i) 35 u=read()+1,v=read()+1,add(u,v),add(v,u); 36 dfs(1,0); 37 for(int i=1;i<=n;++i) cmax(d,dep[i]); 38 if(m<=d) return printf("%d ",m),0; 39 printf("%d ",min(n,d+(m-d+1)/2)); 40 return 0; 41 }