记录编号	481532	评测结果	AAAAAAAAAAAAAAAA
题目名称	[IOI 2011] Race	最终得分	100
用户昵称	Hallmeow	是否通过	通过
代码语言	C++	运行时间	3.211 s
提交时间	2018-01-03 11:32:34	内存使用	9.70 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define pos(i,a,b) for(int i=(a);i<=(b);++i)
#define pos2(i,a,b) for(int i=(a);i>=(b);--i)
#define N 200100
#define inf 0x7fffffff
char xB[(1<<15)+10],*xS=xB,*xT=xB;
#define gtc (xS==xT&&(xT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xT)?0:*xS++)
inline void read(int &shu){
	register char ch=gtc;
	for(shu=0;ch<'0'||ch>'9';ch=gtc);
	for(;ch>='0'&&ch<='9';shu=(shu<<1)+(shu<<3)+ch-'0',ch=gtc);
}
int n,k;
struct haha{
  	int next,to,w;
}edge[N*2];
int head[N],cnt=1;
inline void add(int u,int v,int w){
  	edge[cnt].w=w;
  	edge[cnt].to=v;
  	edge[cnt].next=head[u];
  	head[u]=cnt++;
}
int root,size[N],dep[N],tot,cntsize;
bool vis[N];
void getroot(int x,int fa){
	size[x]=1;int res(0);
	for(int i=head[x];i;i=edge[i].next){
		int to=edge[i].to;
		if(to!=fa&&!vis[to]){
			getroot(to,x);
			size[x]+=size[to];if(size[to]>res) res=size[to];
		}
	}
	if(tot-size[x]>res) res=tot-size[x];
	if(res<cntsize){
		cntsize=res;root=x;
	}
}
int ans[N],hea;
struct xixi{
	int dep,dis;
	bool operator <(const xixi &f)const{
		return dis<f.dis;
	}
}stack[N];
void dfs(int x,int ww,int fa){
	size[x]=1;stack[++hea]=(xixi){dep[x],ww};
	for(int i=head[x];i;i=edge[i].next){
		int to=edge[i].to,w=edge[i].w;
		if(!vis[to]&&to!=fa){
			dep[to]=dep[x]+1;
			dfs(to,ww+w,x);
			size[x]+=size[to];
		}
	}
}
void cal(int x,int dis,int opt){
	hea=0;dep[x]=(opt==1)?0:1;dfs(x,dis,0);
	sort(stack+1,stack+hea+1);
	int l=1,r=hea;
	
	if(k==50){
		while(l<=r){
			if(stack[l].dis+stack[r].dis>k) r--;
			else{
				if(stack[l].dis+stack[r].dis==k) ans[stack[l].dep+stack[r].dep]+=opt;
				l++;
			}
		}
	}
	else{
		while(l<=r){
			while(r>l&&stack[l].dis+stack[r].dis>k) r--;
			for(int i=r;i>l&&stack[l].dis+stack[i].dis==k;i--) ans[stack[l].dep+stack[i].dep]+=opt;
			l++;
		}
	}
}
void work(int x){
	vis[root]=1;
	for(int i=head[x];i;i=edge[i].next){
		int to=edge[i].to;
		if(!vis[to]){
			cal(to,edge[i].w,-1);
		}
	}
	cal(x,0,1);
	for(int i=head[x];i;i=edge[i].next){
		int to=edge[i].to;
		if(!vis[to]){
			tot=size[to];cntsize=inf;getroot(to,x);
			work(root);
		}
	}
}
int main(){
	 freopen("ioi2011-race.in","r",stdin);
	 freopen("ioi2011-race.out","w",stdout);
	int size = 128 << 20;
    char *p = (char*)malloc(size) + size;  
    __asm__("movl %0, %%esp\n" :: "r"(p));


	read(n);read(k);
	pos(i,1,n-1){
		int x,y,z;read(x);read(y);read(z);x++;y++;
		add(x,y,z);add(y,x,z);
	}
	cntsize=inf;tot=n;getroot(1,0);
	work(root);
	pos(i,0,n) if(ans[i]){
		cout<<i;return 0;
	}
	cout<<-1;
	return 0;
}