找以起点为起点的一个最长链，最优一定是在最长链上不走回头路的，所以相当于最长链上的边代价是1，非最长链的边代价是2（因为要走回去），每付出一次代价就可以使访问到的点数+1，那么贪心即可
#include<iostream> #include<cstring> #include<ctime> #include<cmath> #include<algorithm> #include<iomanip> #include<cstdlib> #include<cstdio> #include<map> #include<bitset> #include<set> #include<stack> #include<vector> #include<queue> using namespace std; #define MAXN 1010 #define MAXM 1010 #define ll long long #define eps 1e-8 #define MOD 1000000007 #define INF 1000000000 struct vec{ int to; int fro; }; vec mp[MAXN*2]; int tai[MAXN],cnt; int n,k; int mx[MAXN]; int ans=1; inline void be(int x,int y){ mp[++cnt].to=y; mp[cnt].fro=tai[x]; tai[x]=cnt; } inline void bde(int x,int y){ be(x,y); be(y,x); } void dfs(int x,int f){ int i,y; for(i=tai[x];i;i=mp[i].fro){ y=mp[i].to; if(y!=f){ dfs(y,x); mx[x]=max(mx[x],mx[y]+1); } } } int main(){ int i,x,y; scanf("%d%d",&n,&k); for(i=1;i<n;i++){ scanf("%d%d",&x,&y); bde(x+1,y+1); } dfs(1,0); ans+=min(mx[1],k); k-=min(mx[1],k); while(ans<n&&k>=2){ ans++; k-=2; } printf("%d\n",ans); return 0; } /* */
