记录编号	391823	评测结果	AAAAAAAAAAAAAAAA
题目名称	[IOI 2011] Race	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	2.363 s
提交时间	2017-04-06 19:26:46	内存使用	50.83 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e6+10;
struct edge{int f,t,l;}w[N];
int n,k,nxt[N],head[N],ans=1e9;
void add_edge(int f,int t,int l){
	static int cnt=0;
	w[++cnt]=(edge){f,t,l};
	nxt[cnt]=head[f];
	head[f]=cnt;
}
typedef long long ll;
bool vis[N];
int q[N],size,fa[N],h[N],s[N],big[N],root;
int dp[N];ll dep[N];
void solve(int x){
	q[size=1]=x;fa[x]=x;
	for (int i=1;i<=size;i++){
		int v=q[i];
		s[v]=1;big[v]=0;
		for (int i=head[v];i;i=nxt[i]){
			int u=w[i].t;
			if (fa[u]||vis[u]) continue;
			fa[u]=v;
			q[++size]=u;
		}
	}
	for (int i=size;i;i--){
		int v=q[i];
		if (s[v]>=size/2&&big[v]<=size/2) root=v;
		s[fa[v]]+=s[v];
		big[fa[v]]=max(big[fa[v]],s[v]);
		fa[v]=0;
	}
	vis[root]=1;
	dp[0]=size=0;
	for (int i=head[root];i;i=nxt[i]){
		int S=w[i].t,last=size;
		if (vis[S]) continue;
		fa[S]=S;
		dep[S]=w[i].l;
		h[S]=1;
		q[++size]=S;
		for (int i=size;i<=size;i++){
			int v=q[i];
			if (dep[v]<=k) ans=min(ans,h[v]+dp[k-dep[v]]);
			for (int i=head[v];i;i=nxt[i]){
				int u=w[i].t;
				if (fa[u]||vis[u]) continue;
				fa[u]=v;
				dep[u]=dep[v]+w[i].l;
				h[u]=h[v]+1;
				q[++size]=u;
			}
		}
		for (int i=last+1;i<=size;i++){
			int v=q[i];
			if (dep[v]<=k) dp[dep[v]]=min(dp[dep[v]],h[v]);
		}
	}
	for (int i=1;i<=size;i++){
		int v=q[i];
		fa[v]=0;
		if (dep[v]<=k) dp[dep[v]]=1e9;
	}
	for (int i=head[root];i;i=nxt[i])
		if (!vis[w[i].t]) solve(w[i].t);
}
int main()
{
	freopen("ioi2011-race.in","r",stdin);
	freopen("ioi2011-race.out","w",stdout);
	scanf("%d%d",&n,&k);
	for (int i=1;i<n;i++){
		int u,v,l;
		scanf("%d%d%d",&u,&v,&l);
		u++;v++;
		add_edge(u,v,l);
		add_edge(v,u,l);
	}
	for (int i=0;i<=k;i++) dp[i]=1e9;
	solve(1);
	printf("%d\n",ans>=n?-1:ans);
	return 0;
}