淀粉质真好吃（点分治）

#include<bits/stdc++.h>
#define N 200005
#define M 1000006
#define inf 10000007
using namespace std;
struct oppo{
    int to,w,next;
}rood[N*2];
int head[N],tot;
void add(int from,int to,int w)
{
    rood[++tot].to=to;
    rood[tot].next=head[from];
    rood[tot].w=w;
    head[from]=tot;
}
int n,k,sum,ans=999999;
int s,t,d;
bool vis[N];
int rt;
int maxp[N];
int siz[N];
void getrt(int x,int fa)
{
    maxp[x]=0,siz[x]=1;
    for(int i=head[x];i;i=rood[i].next){
        int to=rood[i].to;
        if(to==fa||vis[to]) 
            continue;
        getrt(to,x);
        maxp[x]=max(maxp[x],siz[to]);
        siz[x]+=siz[to];
    }
    maxp[x]=max(sum-siz[x],maxp[x]);
    if(maxp[x]<maxp[rt])
        rt=x;
}
int rem[N];
int dis[N];
bool flag[M];
int dep[N];
int bs[N];
int minbs[M];
void getdis(int x,int fa)
{
    if(dis[x]>k)
        return;
    rem[++rem[0]]=dis[x];
    bs[++bs[0]]=dep[x];
    for(int i=head[x];i;i=rood[i].next)
    {
        int to=rood[i].to;
        if(vis[to]||to==fa)
            continue;
        dis[to]=dis[x]+rood[i].w;
        dep[to]=dep[x]+1;
        getdis(to,x);
    }
}
queue< int > v;
void laca(int x)
{
    flag[0]=1;
    minbs[0]=0;
    for(int i=head[x];i;i=rood[i].next)
    {
        int to=rood[i].to;
        if(vis[to])
            continue;
        rem[0]=bs[0]=0;
        dis[to]=rood[i].w;
        dep[to]=1;
        getdis(to,-1);
        for(int j=1;j<=rem[0];j++)
        {
            //cout<<rem[j]<<"--"<<bs[j]<<endl;
            if(k>=rem[j]&&flag[k-rem[j]])
                ans=min(ans,bs[j]+minbs[k-rem[j]]);
        }
        for(int j=1;j<=rem[0];j++){
            v.push(rem[j]);
            flag[rem[j]]=1;
            minbs[rem[j]]=min(minbs[rem[j]],bs[j]);
        }
    }
    while(v.size()){
        int fr=v.front();
        flag[fr]=0;
        minbs[fr]=inf;
        v.pop();
    }
}
void work(int x)
{
    vis[x]=1;
    laca(x);
    for(int i=head[x];i;i=rood[i].next)
    {
        int to=rood[i].to;
        if(vis[to])
            continue;
        maxp[rt=0]=inf;
        sum=siz[to];
        getrt(to,-1);
        getrt(to,-1);
        work(rt);
    }
}
int main()
{
    memset(minbs,10,sizeof(minbs));
    cin>>n>>k;
    for(int i=1;i<n;i++){
        scanf("%d%d%d",&s,&t,&d);
        add(s,t,d);
        add(t,s,d);
    }
    maxp[rt=0]=inf;
    sum=n;
    getrt(rt,-1);
    getrt(rt,-1);
    work(rt);
    if(ans==999999) ans=-1;
    cout<<ans<<endl;
    return 0;
}