全 RE 还行。

dark bzoj 可过。

namespace Point_Division {
	#define v now.to
	ll dis[N];
	int rt,all,ans,cnt,dp[K],val[N],siz[N],vis[N],tot[N];
	std::pair <ll,int> sta[N];

	void get_siz(int u,int fa) {
		siz[u]=1;
		for(Node now:son[u])
			if(!vis[v]&&v!=fa) get_siz(v,u),siz[u]+=siz[v];
	}
	void get_rt(int u,int fa) {
		val[u]=0;
		for(Node now:son[u])
			if(!vis[v]&&v!=fa) get_rt(v,u),chkmax(val[u],siz[v]);
		chkmax(val[u],all-siz[u]);
		if(val[u]<val[rt]) rt=u;
	}
	void get_dis(int u,int fa,int las) {
		dis[u]=dis[fa]+las,tot[u]=tot[fa]+1;
		for(Node now:son[u]) if(!vis[v]&&v!=fa) get_dis(v,u,now.val);
		sta[++cnt]=mkp(dis[u],tot[u]);
	}
	inline int calc(int u) {
		cnt=0,dis[u]=tot[u]=dp[0]=0;
		for(Node now:son[u]) if(!vis[v]) {
			int las=cnt+1;
			get_dis(v,u,now.val);
			for(int i=las;i<=cnt;++i)
				if(sta[i].fi<=k) chkmin(ans,dp[k-sta[i].fi]+sta[i].se);
			for(int i=las;i<=cnt;++i)
				if(sta[i].fi<=k) chkmin(dp[sta[i].fi],sta[i].se);
		}
		for(int i=1;i<=cnt;++i) if(sta[i].fi<=k) dp[sta[i].fi]=inf;
	}
	void solve(int u) {
		vis[u]=true,calc(u),get_siz(u,0);
		for(Node now:son[u]) if(!vis[v])
			rt=0,all=siz[v],get_rt(v,0),solve(rt);
	}
	#undef v
} using namespace Point_Division;