P4149 [IOI 2011] Race

Given a tree with a weight on each edge, find a simple path whose total weight equals $k$, with the minimum possible number of edges.

The first line contains two integers $n, k$, representing the number of vertices in the tree and the target path sum. Each of the next $n-1$ lines contains three integers $u_i, v_i, w_i$, representing an undirected edge between $u_i$ and $v_i$ with weight $w_i$. **Note: vertices are numbered starting from $0$.**

Output a single integer, the minimal number of edges. If no such path exists, output $-1$.

For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 2 \times 10^5$, $0 \leq k, w_i \leq 10^6$, $0 \leq u_i, v_i < n$. Translated by ChatGPT 5