求助点分治75pts

#include <iostream>
#include <vector>
#define mn 200010
#define T tr[now]
#define inf 0x3f3f3f3f
using namespace std;
int n, K;
int ans = inf;

struct treap
{
    int ls, rs;
    int val;
    int dep;
    int siz;
    int rnd;
} tr[mn];
int root, cnt;
int x, y, z, w;

inline void pushup(int now)
{
    T.siz = tr[T.ls].siz + tr[T.rs].siz + 1;
}

inline void split(int now, int k, int dep, int &x, int &y)
{
    if (!now)
    {
        x = y = 0;
        return;
    }
    if (T.val < k)
    {
        x = now;
        split(T.rs, k, dep, T.rs, y);
    }
    else if (T.val > k)
    {
        y = now;
        split(T.ls, k, dep, x, T.ls);
    }
    else
    {
        if (T.dep <= dep)
        {
            x = now;
            split(T.rs, k, dep, T.rs, y);
        }
        else
        {
            y = now;
            split(T.ls, k, dep, x, T.ls);
        }
    }
    pushup(now);
}

inline int merge(int A, int B)
{
    if (!A || !B)
        return A | B;
    if (tr[A].rnd < tr[B].rnd)
    {
        tr[A].rs = merge(tr[A].rs, B);
        pushup(A);
        return A;
    }
    else
    {
        tr[B].ls = merge(A, tr[B].ls);
        pushup(B);
        return B;
    }
}

inline int add(int k, int dep)
{
    tr[++cnt].val = k;
    tr[cnt].dep = dep;
    tr[cnt].siz = 1;
    tr[cnt].rnd = rand();
    return cnt;
}

inline void ins(int k, int dep)
{
    split(root, k, dep, x, y);
    root = merge(merge(x, add(k, dep)), y);
}

inline int kth(int now, int k)
{
    while (1)
    {
        if (k <= tr[T.ls].siz)
            now = T.ls;
        else if (k == tr[T.ls].siz + 1)
            return T.dep;
        else
        {
            k -= tr[T.ls].siz + 1;
            now = T.rs;
        }
    }
}

inline int getrk(int k)
{
    split(root, k - 1, inf, x, y);
    split(y, k, inf, y, w);
    split(y, k, -1, y, z);
    if (!z)
        return inf;
    int res = kth(z, 1);
    root = merge(merge(merge(x, y), z), w);
    return res;
}

inline void clear()
{
    for (int i = 1; i <= cnt; ++i)
        tr[i].ls = tr[i].rs = 0;
}

struct node
{
    int to;
    int val;
};
vector<node>G[mn];
int siz[mn];
int vis[mn];
int rt, rt_siz;
int tr_siz;

inline void getsiz(int u, int fa)
{
    siz[u] = 1;
    for (node v : G[u])
    {
        if (v.to == fa || vis[v.to])
            continue;
        getsiz(v.to, u);
        siz[u] += siz[v.to];
    }
}

inline void getrt(int u, int fa)
{
    int max_part = 0;
    for (node v : G[u])
    {
        if (v.to == fa || vis[v.to])
            continue;
        getrt(v.to, u);
        max_part = max(max_part, siz[v.to]);
    }
    max_part = max(max_part, tr_siz - siz[u]);
    if (max_part < rt_siz)
    {
        rt_siz = max_part;
        rt = u;
    }
}

inline void count(int u, int fa, int k, int dep)
{
    if (k > K)
        return;
    ans = min(ans, getrk(K - k) + dep);
    for (node v : G[u])
    {
        if (v.to == fa || vis[v.to])
            continue;
        count(v.to, u, k + v.val, dep + 1);
    }
}

inline void update(int u, int fa, int k, int dep)
{
    ins(k, dep);
    for (node v : G[u])
    {
        if (v.to == fa || vis[v.to])
            continue;
        update(v.to, u, k + v.val, dep + 1);
    }
}

inline void solve(int u, int fa)
{
    getsiz(u, fa);
    tr_siz = siz[u];
    rt = 0, rt_siz = inf;
    getrt(u, fa);
    u = rt;
    vis[u] = 1;
    ins(0, 0);
    for (node v : G[u])
    {
        if (v.to == fa || vis[v.to])
            continue;
        count(v.to, u, v.val, 1);
        update(v.to, u, v.val, 1);
    }
    clear();
    root = cnt = 0;
    for (node v : G[u])
    {
        if (v.to == fa || vis[v.to])
            continue;
        solve(v.to, u);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> K;
    for (int i = 1, u, v, w; i <= n - 1; ++i)
    {
        cin >> u >> v >> w;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }
    solve(0, -1);
    if (ans > n)
        cout << -1;
    else
        cout << ans;
    return 0;
}