记录编号	600150	评测结果	AAAAAAAAAAAAAAAA
题目名称	[IOI 2011] Race	最终得分	100
用户昵称	djyqjy	是否通过	通过
代码语言	C++	运行时间	2.209 s
提交时间	2025-04-16 22:24:00	内存使用	16.18 MiB

#include<bits/stdc++.h>
using namespace std;
inline int re()
{
    int f=1,num=0;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
    return num*f;
}
const int N=200010,Z=1000010;
int n,k,rt,jsq,ans=INT_MAX;
int ver[2*N],edge[2*N],nxt[2*N],hd[N],sz[N],maxs[N],vis[N],mine[Z],w[N],depth[N];
int jsqb=1;
inline void add_edge(int x,int y,int z)
{
    ver[++jsqb]=y;
    edge[jsqb]=z;
    nxt[jsqb]=hd[x];
    hd[x]=jsqb;
    ver[++jsqb]=x;
    edge[jsqb]=z;
    nxt[jsqb]=hd[y];
    hd[y]=jsqb;
    return;
}
void get_root(int x,int fa,int all)
{
    sz[x]=1;maxs[x]=0;
    for(int i=hd[x];i;i=nxt[i])
    {
        int y=ver[i];
        if(vis[y]||y==fa) continue;
        get_root(y,x,all);
        sz[x]+=sz[y];maxs[x]=max(maxs[x],sz[y]);
    }
    maxs[x]=max(maxs[x],all-sz[x]);
    if(!rt||maxs[x]<maxs[rt]) rt=x;
    return;
}
void get_dis(int x,int fa,int d1,int d2)//d1:w,d2:depth
{
    if(d1>k) return;
    w[++jsq]=d1;depth[jsq]=d2;
    for(int i=hd[x];i;i=nxt[i])
    {
        int y=ver[i];
        if(vis[y]||y==fa) continue;
        get_dis(y,x,d1+edge[i],d2+1);
    }
    return;
}
void get_all(int x)
{
    vis[x]=1;
    mine[0]=jsq=0;
    for(int i=hd[x],last;i;i=nxt[i])
    {
        int y=ver[i];
        if(vis[y]) continue;
        last=jsq+1;
        get_dis(y,x,edge[i],1);
        for(int j=last;j<=jsq;j++) ans=min(ans,mine[k-w[j]]+depth[j]);
        for(int j=last;j<=jsq;j++) mine[w[j]]=min(mine[w[j]],depth[j]);
    }
    for(int i=1;i<=jsq;i++) mine[w[i]]=0x3f3f3f3f;
    for(int i=hd[x];i;i=nxt[i])
    {
        int y=ver[i];
        if(vis[y]) continue;
        rt=0;get_root(y,x,sz[y]);
        get_all(rt);
    }
    return;
}
int main()
{
    freopen("ioi2011-race.in","r",stdin);
    freopen("ioi2011-race.out","w",stdout);
    n=re();k=re();
    for(int i=1,x,y,z;i<n;i++) x=re()+1,y=re()+1,z=re(),add_edge(x,y,z);
    get_root(1,0,n);
    memset(mine,0x3f,sizeof(mine));
    get_all(rt);
    if(ans>=0x3f3f3f3f) printf("-1");
    else printf("%d",ans);
    return 0;
}