记录编号	392088	评测结果	AAAAAAAAAAAAAAAA
题目名称	[IOI 2011] Race	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	1.972 s
提交时间	2017-04-07 07:38:58	内存使用	14.98 MiB

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
char cc;inline void R_int(int &x){
	while(cc=getchar(),cc<'!');x=cc-48;
	while(cc=getchar(),cc>'!')x=x*10+cc-48;
}
const int maxn=200005,INF=0x3f3f3f3f;
struct Rabit_tree{int to,next,dis;}e[maxn<<1];int us[1000005],tim=0,mp[1000005];
int n,K,head[maxn],len=1,size[maxn],mx[maxn],RT,Sz,ans=INF;bool vis[maxn];
void Set(int prt,int son,int dis){
	e[++len].to=son,e[len].next=head[prt],head[prt]=len,e[len].dis=dis;
}
#define to e[i].to
void Rabit_in(){
	R_int(n),R_int(K);int i,x,y,z;
	for(i=1;i<n;i++)R_int(x),R_int(y),x++,y++,R_int(z),Set(x,y,z),Set(y,x,z);
}
void Get(int rt,int fa){
	size[rt]=1,mx[rt]=0;
	for(int i=head[rt];i;i=e[i].next)
		if(!vis[to]&&to^fa)Get(to,rt),size[rt]+=size[to],mx[rt]=max(mx[rt],size[to]);
	mx[rt]=max(mx[rt],Sz-size[rt]);
	if(mx[rt]<mx[RT])RT=rt;
}
void Run(int rt,int fa,int Dp,int dis){
	if(dis>K)return;
	if(us[K-dis]==tim)ans=min(ans,Dp+mp[K-dis]);
	for(int i=head[rt];i;i=e[i].next)
		if(to^fa&&!vis[to])Run(to,rt,Dp+1,dis+e[i].dis);
}
void Set(int rt,int fa,int Dp,int dis){
	if(dis>K)return;
	if(us[dis]^tim)us[dis]=tim,mp[dis]=Dp;else mp[dis]=min(mp[dis],Dp);
	for(int i=head[rt];i;i=e[i].next)
		if(to^fa&&!vis[to])Set(to,rt,Dp+1,dis+e[i].dis);
}
void Get(int rt){
	us[0]=++tim,mp[0]=0;
	for(int i=head[rt];i;i=e[i].next)
		if(!vis[to])Run(to,0,1,e[i].dis),Set(to,0,1,e[i].dis);
}
void Run(int rt){
	vis[rt]=true;Get(rt);
	for(int i=head[rt];i;i=e[i].next)
		if(!vis[to])Sz=size[to],RT=0,Get(to,0),Run(RT);
}
#define APPLY_LANGER_STACK \
	int __size__=32<<20; \
	char *__p__=(char*)malloc(__size__)+__size__; \
	__asm__("movl %0, %%esp\n"::"r"(__p__))
int main(){
	freopen("ioi2011-race.in","r",stdin);freopen("ioi2011-race.out","w",stdout);
	APPLY_LANGER_STACK;
	Rabit_in(),mx[RT=0]=maxn,Sz=n,Get(1,0),Run(RT);
	printf("%d\n",ans<INF?ans:-1);
	fclose(stdin);fclose(stdout);return 0;
}