难道有玄学复杂度？

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#define LL long long
#define Re register int
using namespace std;
const int N=1e6+3,M=1e6+3;
int x,y,n,K,o=1,id_O,head[N];bool pan[N],panc[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
int st,cnt,cir[N];bool In[N];
inline int find_circle(Re x,Re p){
	if(In[x]){st=x,cir[++cnt]=x,pan[x]=1;return 1;}
	In[x]=1;
	for(Re i=head[x];i;i=a[i].next)
		if(i!=(p^1)&&find_circle(a[i].to,i)){
			pan[x]=1;
			if(x==st)return 0;
			cir[++cnt]=x;
			return 1;
		}
	return 0;
}
int root,id[N],size[N];bool pan1[N];
inline void dfs1(Re x){
	pan1[x]=1,++size[id[x]=id_O],root=min(root,x);
	for(Re i=head[x],to;i;i=a[i].next)
		if(!pan1[to=a[i].to])dfs1(to);
}
int w1[M],w2[M],w11_t,w11[N];
int Sw11;
bool pan3[N];
inline int dfs3(Re x){
	Re ans=1;pan3[x]=1;
	for(Re i=head[x],to;i;i=a[i].next)
		if(!pan3[to=a[i].to])ans+=dfs3(to);
	return ans;
}
inline void sakura(Re x){
	root=x,dfs1(x);
	
	cnt=st=0;find_circle(x=root,0);
	for(Re i=1;i<=cnt;++i)panc[cir[i]]=1;
	
	if(panc[x]){//¸ùÔÚ»·ÉÏ,w1»·ÉÏÆäËûλÖÃÉϵĵ¥¸î£¬w2×Ô¼ºÕâÀïµÄË«¸î£¬w11×Ô¼ºÕâÀﻥ²»Ó°ÏìµÄµ¥¸î 
		LL ans1=0,ans2=0;
		for(Re o=1;o<=cnt;++o)
			if(cir[o]!=x){
				pan3[cir[o]]=1;
				for(Re i=head[cir[o]];i;i=a[i].next)
					if(!panc[a[i].to])w1[id_O]=max(w1[id_O],dfs3(a[i].to));
			}
			else{//cir[o]==x
				pan3[cir[o]]=1,Sw11=0;
				for(Re i=head[cir[o]];i;i=a[i].next)
					if(!panc[a[i].to]){
						Re tmp=dfs3(a[i].to);
						w11[++w11_t]=tmp,Sw11+=tmp;
					}
				w2[id_O]=size[id_O]-Sw11-1;
			}
	}
	else{//¸ù²»ÔÚ»·ÉÏ
		pan3[x]=1;
		for(Re i=head[x];i;i=a[i].next)
			w11[++w11_t]=dfs3(a[i].to);
	}
//	printf("id=%d, root=%d, size=%d:\n",id_O,root[id_O],size[id_O]);
//	printf("w1=%d, w2=%d, w11=",w1[id_O],w2[id_O]);
//	for(Re i=0;i<(int)w11[id_O].size();++i)printf("%d ",w11[id_O][i]);
//	puts("");
}
int S[N],dp[2][N];
int main(){
//	freopen("123.txt","r",stdin);
//	freopen("my.out","w",stdout);
	in(n),in(K);
	for(Re i=1;i<=n;++i)in(x),in(y),add(x,y),add(y,x);
	for(Re i=1;i<=n;++i)if(!pan1[i])++id_O,sakura(i);
	int now=0;
	for(Re i=0;i<=n;++i)dp[0][i]=dp[1][i]=-1e9;
	dp[now][0]=0;
	int T=0,limit=n;
//	printf("w11_t=%d\n",w11_t);

//	sort(w11+1,w11+w11_t+1);
//	for(Re i=w11_t;i>=1;--i){
//		Re up=min(T+1,limit);
//		for(Re j=up;j>=1;--j){
//			dp[now][j]=max(dp[now][j],dp[now][j-1]+w11[i]);
//			if(dp[now][j]>=K)limit=j;
//		}
//		T+=1,T=min(T,limit);
//	}

//	for(Re j=T;j>=0;--j)printf("dp[%d]=%d\n",j,dp[now][j]);
	for(Re id=1;id<=id_O;++id)if(w2[id]){
//		printf("w2[%d]=%d, w1[%d]=%d\n",id,w2[id],id,w1[id]);
		for(Re j=0;j<=T;++j)dp[now^1][j]=dp[now][j];
		for(Re j=0;j<=T;++j){
			dp[now^1][j+1]=max(dp[now^1][j+1],dp[now][j]+w1[id]),
			dp[now^1][j+2]=max(dp[now^1][j+2],dp[now][j]+w2[id]);
			if(j+1<limit&&dp[now^1][j+1]>=K)limit=j+1;
			if(j+2<limit&&dp[now^1][j+2]>=K)limit=j+2;
		}
		T+=2,now^=1;
	}
	sort(w11+1,w11+w11_t+1);
//	for(Re i=w11_t;i>=1;--i)printf("%d ",w11[i]);puts("");
	for(Re i=w11_t;i>=1;--i)S[w11_t-i+1]=S[w11_t-i+1-1]+w11[i];
//	for(Re i=1;i<=w11_t;++i)printf("%d ",S[i]);puts("");
	Re up=min(T+1,limit),ans=limit;
	for(Re j=0;j<=up;++j){
		Re tmp=K-dp[now][j];
		if(S[w11_t]<tmp)continue;
		Re l=1,r=w11_t;
		while(l<r){
			Re mid=(l+r>>1);
			if(S[mid]<tmp)l=mid+1;
			else r=mid;
		}
//		printf("j=%d l=%d, dp=%d, S=%d\n",j,l,dp[now][j],S[l]);
		ans=min(ans,j+l);
	}
	printf("%d",ans);
    return 0;
}