记录编号	390923	评测结果	AAAAAAAAAAAAAAAA
题目名称	[IOI 2011] Race	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	2.441 s
提交时间	2017-04-04 17:02:47	内存使用	19.63 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define Inf 2e9
const int maxn=250000;
struct Edge{
	int next,to,dis;
}e[maxn<<1];
int len,head[maxn];
void Insert(int x,int y,int z){
	len++;e[len].to=y;e[len].dis=z;e[len].next=head[x];head[x]=len;
}
int n,K;
int RT,sum,Max[maxn],size[maxn];
bool vis[maxn];
void getroot(int x,int fa){
	size[x]=1;Max[x]=0;
	for(int i=head[x];i;i=e[i].next){
		int j=e[i].to;
		if(!vis[j] && j!=fa){
			getroot(j,x);
			size[x]+=size[j];
			Max[x]=max(Max[x],size[j]);
		}
	}
	Max[x]=max(Max[x],sum-size[x]);
	if(Max[x]<Max[RT]) RT=x;
}
int ans=Inf;
int dis[maxn],Count[1000500];
int deep[maxn],now[maxn],cnt;
int VIS[1000500],Tim;
void Dfs(int x,int fa,int dep){
	deep[++cnt]=dis[x];
	now[cnt]=dep;
	for(int i=head[x];i;i=e[i].next){
		int j=e[i].to;
		if(!vis[j] && j!=fa){
			dis[j]=dis[x]+e[i].dis;
			if(dis[j]>K) continue;
			Dfs(j,x,dep+1);
		}
	}
}
void calc(int x){
	Tim++;
	dis[x]=0;
	Count[0]=0;VIS[0]=Tim;
	for(int i=head[x];i;i=e[i].next){
		int j=e[i].to;
		if(vis[j])continue;
		dis[j]=dis[x]+e[i].dis;
		if(dis[j]>K) continue;
		cnt=0;
		Dfs(j,0,1);
		for(int k=1;k<=cnt;k++) {
			if(VIS[K-deep[k]]!=Tim) {Count[K-deep[k]]=2e8;VIS[K-deep[k]]=Tim;}
			ans=min(ans,now[k]+Count[K-deep[k]]);
		}
		for(int k=1;k<=cnt;k++){
			if(VIS[deep[k]]!=Tim) {Count[deep[k]]=2e8;VIS[deep[k]]=Tim;}
			Count[deep[k]]=min(Count[deep[k]],now[k]);
		}
	}
}
void Solve(int x){
	vis[x]=true;
	calc(x);
	for(int i=head[x];i;i=e[i].next){
		int j=e[i].to;
		if(!vis[j]){
			RT=0;sum=size[j];
			getroot(j,0);
			Solve(RT);
		}
	}
}
void Init();
int main(){
	int __size__=128<<20;
	char *__p__=(char*)malloc(__size__)+__size__;
	__asm__("movl %0, %%esp\n"::"r"(__p__));
	freopen("ioi2011-race.in","r",stdin);
	freopen("ioi2011-race.out","w",stdout);
	Init();
	return 0;
}
void Init(){
	scanf("%d%d",&n,&K);
	for(int i=1;i<n;i++){
		int x,y,z;scanf("%d%d%d",&x,&y,&z);
		x++;y++;
		Insert(x,y,z);Insert(y,x,z);
	}
	RT=0;Max[RT]=Inf;sum=n;
	getroot(1,0);
	Solve(RT);
	if(ans>n) puts("-1");
	else printf("%d\n",ans);
}