题目传送门

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,K=1e6+5;
int n,k,rt,all,cnt,ans=1e9;
int maxx[N],siz[N],dis[N],vis[N],ec[N],f[K];
vector<int> g[N],w[N],rec;
void get_cog(int u,int las)//求重心 
{
	siz[u]=1;
	maxx[u]=0;
	for(int i=0;i<g[u].size();i++)
	{
		int v=g[u][i];
		if(v==las||vis[v]) continue;
		get_cog(v,u);
		maxx[u]=max(maxx[u],siz[v]);
		siz[u]+=siz[v];
	}
	maxx[u]=max(maxx[u],all-siz[u]);
	if(maxx[u]<=all/2) rt=u;
}
void get_dis(int u,int las,int sum,int ecnt) 
{
	if(sum>k) return ;
	dis[++cnt]=sum; ec[cnt]=ecnt;
	for(int i=0;i<g[u].size();i++)
	{
		int v=g[u][i];
		if(vis[v]||v==las) continue;
		get_dis(v,u,sum+w[u][i],ecnt+1);
	}
}
void calc(int u)
{
	vis[u]=1; f[0]=0; cnt=0;
	for(int i=0;i<g[u].size();i++)
	{
		int v=g[u][i]; 
		if(vis[v]) continue;
		int pre=cnt;
		get_dis(v,u,w[u][i],1);
		for(int j=pre+1;j<=cnt;j++) ans=min(ans,f[k-dis[j]]+ec[j]);
		for(int j=pre+1;j<=cnt;j++) f[dis[j]]=min(f[dis[j]],ec[j]);
	}
	for(int i=1;i<=cnt;i++) f[dis[i]]=1e9;
	for(int i=0;i<g[u].size();i++)
	{
		int v=g[u][i];
		if(vis[v]) continue;
		all=siz[v]; rt=0;
		get_cog(v,u);
		calc(rt);
	}
}
int main()
{
	scanf("%d%d",&n,&k);
	int x,y,z;
	for(int i=1;i<n;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		x++; y++;
		g[x].push_back(y); g[y].push_back(x);
		w[x].push_back(z); w[y].push_back(z);
	}
	maxx[0]=n+1; all=n;
	get_cog(1,0);
	fill(f,f+K,1e9);
	calc(rt);
	printf("%d",ans>=n?-1:ans);
}

（话说，我翻了最近20页的提交记录，非匿名用户只有3个人是95改到100的，于是我带着希望分析了他们前后代码的差异，发现2个对我没有帮助，剩下1个是特判数据的。。。）