评测记录

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int tot,to[N<<1],nx[N<<1],st[N],co[N<<1];
void add(int x,int y,int w){
	to[++tot]=y,nx[tot]=st[x],st[x]=tot,co[tot]=w;;
}
int vis[N],sz[N],min1,as;
void dfs1(int x,int y){
	sz[x]=1;
	for(int i=st[x];i;i=nx[i]){
		int v=to[i];
		if(v!=y&&!vis[v])dfs1(v,x),sz[x]+=sz[v];
	}
}
void dfs2(int rt,int x,int y){
	int max1=sz[rt]-sz[x];
	for(int i=st[x];i;i=nx[i]){
		int v=to[i];
		if(v!=y&&!vis[v])dfs2(rt,v,x),max1=max(max1,sz[v]);
	}
	if(max1<min1)min1=max1,as=x;
}
int ans=N;
int cnt[(int)1e6+5];
int zhong(int x){
	dfs1(x,0);
	min1=N;
	dfs2(x,x,0);
	return as;
}
int b[N],bs,c[N],cs;
int dep[N],l[N];
int k;
void calc(int x,int y,int len){
	if(len>k)return;
	b[++bs]=x;
	dep[x]=dep[y]+1;
	if(len==k)ans=min(ans,dep[x]);
	l[x]=len;
	for(int i=st[x];i;i=nx[i]){
		int v=to[i];
		if(v!=y&&!vis[v]){
			calc(v,x,len+co[i]);
		}
	}
}
void dfs(int x){
	x=zhong(x);
	cs=0;
	for(int i=st[x];i;i=nx[i]){
		int v=to[i];
		if(!vis[v]){
			bs=0;
			calc(v,x,co[i]);
			for(int i=1;i<=bs;i++){
				ans=min(ans,dep[b[i]]+cnt[k-l[b[i]]]);
			}
			for(int i=1;i<=bs;i++){
				c[++cs]=b[i];
				cnt[l[b[i]]]=min(cnt[l[b[i]]],dep[b[i]]);
			}
		}
		
	}
	for(int i=1;i<=cs;i++)cnt[l[c[i]]]=N;
	vis[x]=1;
	for(int i=st[x];i;i=nx[i]){
		int v=to[i];
		if(!vis[v])dfs(v);
	}
}
int n;
int main(){
//	freopen("1.in","r",stdin);
	memset(cnt,0x3f,sizeof cnt);
	scanf("%d%d",&n,&k);
	for(int i=1;i<n;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w),add(v,u,w);
	}
	dfs(0);
	if(k==0)ans=0;
	if(ans==N)cout<<-1;
	else cout<<ans;
}