前言:

从12点T到下午三点,原本以为ioi是个大毒瘤.
1.卡vector.
2.卡unordered_map/map.
3.卡清空方式.
结果!!!什么都不卡,tm find root之后不搜root,直接搜子节点,我真是个大***...

思路:

直接点分治即可..都没啥好讲的,就是个板子.

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5,M=1e6+6;
struct node{
    int to,val;
}; 
vector<node>g[N];
int n,k,root,f[N],sz[N],sum,ans=1e9;
bool vis[N];
int num[M],id,tot[M];//存每个值存在的最小层数. 
void f_root(int u,int fa)
{
    sz[u]=1,f[u]=0;
    for(auto v:g[u])
    {
        if(v.to==fa||vis[v.to])    continue;
        f_root(v.to,u);sz[u]+=sz[v.to];
        if(sz[v.to]>f[u]) f[u]=sz[v.to];
    }f[u]=max(f[u],sum-sz[u]);
    if(f[u]<f[root])    root=u;
}
void cnt_node(int u,int fa,int dep,int val)
{
    if(val>k)    return;
    if(num[val]!=1e9)    num[val]=min(dep,num[val]);
    else                num[val]=dep,tot[++id]=val;
    for(auto v:g[u])
    {
        if(vis[v.to]||v.to==fa)    continue;
        cnt_node(v.to,u,dep+1,val+v.val);
    }
}

void cnt_ans(int u,int fa,int dep,int val)
{
    if(val>k)    return;
    ans=min(ans,num[k-val]+dep);
    for(auto v:g[u])
    {
        if(vis[v.to]||v.to==fa)    continue;
        cnt_ans(v.to,u,dep+1,val+v.val);
    }
}

void cal(int u)
{
    for(auto v:g[u])
    {
        if(vis[v.to])    continue;
        cnt_ans(v.to,u,1,v.val);
        cnt_node(v.to,u,1,v.val);    
    }
}

void solve(int u,int siz)
{
    cal(u);vis[u]=true;
    for(int i=1;i<=id;i++)    num[tot[i]]=1e9;id=0;
    for(auto v:g[u])
    {
        if(vis[v.to])    continue;
        root=0,sum=((sz[v.to]>sz[u])?(siz-sz[u]):sz[v.to]);
        f_root(v.to,u);
        solve(root,sum);
    }
}

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=k;i++)    num[i]=1e9;
    for(int i=1;i<n;i++)
    {
        int u,v,w;scanf("%d%d%d",&u,&v,&w);
        u++,v++;g[u].push_back({v,w});
        g[v].push_back({u,w});
    }f[0]=n,sum=n,root=0;
    f_root(1,0);solve(root,n);
    if(ans!=1e9)     printf("%d\n",ans);
    else            puts("-1");
    return 0;
}