【题意】

求树上的权值和为k的路径包含最少边数

【分析】

仍然是比较明显的点分治

考虑记录一个l[i]表示权值为i的路径最少边数，得到一个子树的所有点到根的路径，更新答案即可

【代码】

#include<bits/stdc++.h>
using namespace std;
const int maxn=4e5+5;
const int maxm=1e6+5;
const int inf=0x3f3f3f3f;
int n,k;
int head[maxn],tot,vis[maxn];
struct edge
{
    int to,nxt,v;
}e[maxn<<1];
void add(int x,int y,int z)
{
    e[++tot].to=y; e[tot].nxt=head[x]; e[tot].v=z; head[x]=tot;
}
int root,siz[maxn],gsiz,size,f,cnt;
int l[maxm],sum[maxn],tong[maxn];
void findrt(int u,int fa)
{
    siz[u]=1;
    int maxnum=0;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int to=e[i].to;
        if(to==fa || vis[to]) continue;
        findrt(to,u);
        siz[u]+=siz[to];
        maxnum=max(maxnum,siz[to]);
    }
    maxnum=max(maxnum,size-siz[u]);
    if(maxnum<gsiz)
    {
        gsiz=maxnum;
        root=u;
        f=fa;
    }
}
int ans;
void query(int u,int fa,int len,int dep)
{
    if(len>k) return;
    ans=min(ans,dep+l[k-len]);
    tong[++cnt]=len; sum[cnt]=dep;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int to=e[i].to;
        if(to==fa || vis[to]) continue;
        query(to,u,len+e[i].v,dep+1);
    }
}
void solve(int u)
{
    for(int i=head[u];i;i=e[i].nxt)
    {
        int to=e[i].to;
        if(vis[to]) continue;
        int temp=cnt;
        query(to,u,e[i].v,1);
        for(int j=temp+1;j<=cnt;j++)
            l[tong[j]]=min(l[tong[j]],sum[j]);
    }
    for(int i=1;i<=cnt;i++) l[tong[i]]=inf;
    l[0]=0; cnt=0;
}
void divide(int u)
{
    vis[u]=1;
    solve(u);
    int kk=f,t=size;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int to=e[i].to;
        if(vis[to]) continue;
        gsiz=inf;
        root=0;
        size=(to!=kk)?siz[to]:(t-siz[u]);
        findrt(to,0);
        divide(root);
    }
}
int main()
{
//    freopen("a.in","r",stdin);
//    freopen("a.out","w",stdout);
    scanf("%d%d",&n,&k);
    int x,y,z;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        x++; y++;
        add(x,y,z); add(y,x,z);
    }
    size=n; gsiz=inf; ans=inf;
    for(int i=1;i<maxm;i++) l[i]=inf;
    findrt(1,0);
    divide(root);
    printf("%d",ans==inf?-1:ans);
    return 0;
}