RT.#2,#7WA,#8TLE.

救救孩子吧QAQ

Code:

#include<bits/stdc++.h>
using namespace std;
#define N 500010
struct edge{
	int v,w,nxt;
}e[N];
int head[N],tot=1;
void ae(int u,int v,int w){
	e[tot]=(edge){v,w,head[u]};
	head[u]=tot++;
}
int n,k;
int rt=0;
int sz[N],dp[N],vst[N];
void getrt(int u,int fa,int sum){
	dp[u]=0,sz[u]=1;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==fa||vst[v])continue;
		getrt(v,u,sum);
		sz[u]+=sz[v];
		dp[u]=max(dp[u],sz[v]);
	}
	dp[u]=max(dp[u],sum-dp[u]);
	if(!rt||dp[u]<dp[rt])rt=u;
}
int ans=0x3f3f3f3f;
int a[N],d1[N],d2[N],b[N],cnt=0;
bool comp(int x,int y){return d1[x]<d1[y];}
void getdep(int u,int fa,int D1,int D2,int x){
	b[u]=x;
	a[cnt++]=u;
	d1[u]=D1;
	d2[u]=D2;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==fa||vst[v])continue;
		getdep(v,u,D1+e[i].w,D2+1,x);
	}
}
void calc(int u){
	cnt=0;
	a[cnt++]=u;
	d1[u]=d2[u]=0;
	b[u]=u;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(vst[v])continue;
		getdep(v,u,e[i].w,1,v);
	}
	sort(a,a+cnt,comp);
	int l=0,r=cnt-1;
	while(l<r){
		if(d1[a[l]]+d1[a[r]]>k)r--;
		else if(d1[a[l]]+d1[a[r]]<k)l++;
		else if(b[a[l]]==b[a[r]]){
			if(d1[a[r]]==d1[r-1])r--;
			else l++;
		}else{
			ans=min(ans,d2[a[l]]+d2[a[r]]);
			if(d1[a[r]]==d1[r-1])r--;
			else l++;
		}
	}
}
void work(int u){
	vst[u]=1;
	calc(u);
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(vst[v])continue;
		rt=0;
		getrt(v,0,sz[v]);
		work(rt);
	}
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=0;i<n-1;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		ae(u,v,w);
		ae(v,u,w);
	}
	getrt(1,0,n);
	work(rt);
	printf("%d\n",ans==0x3f3f3f3f?-1:ans);
	return 0;
}