题目描述

给定一棵 $N$ 个节点的树，每条边带有一个权值。

求一条简单路径，路径上各条边的权值和等于 $K$，且路径包含的边的数量最少。

输入格式

第一行两个整数 $N, K$。

第 $2 \sim N$ 行每行三个整数 $x, y, z$，表示一条无向边的两个端点 $x, y$ 和权值 $z$，点的编号从 $0$ 开始。

输出格式

输出一个整数，表示最少边数量。

如果不存在满足要求的路径，输出 $-1$。

样例

4 3
0 1 1
1 2 2
1 3 4

2

样例解释

树的结构

    0
    |
1---1
|   |
2   3

边权：

• 边 (0,1): 权值 1
• 边 (1,2): 权值 2
• 边 (1,3): 权值 4

寻找权值和为 3 的路径

可能的路径：

1. 0 → 1 → 2：权值和 = 1 + 2 = 3，边数 = 2
2. 0 → 1 → 3：权值和 = 1 + 4 = 5（不符合）
3. 2 → 1 → 3：权值和 = 2 + 4 = 6（不符合）

满足权值和为 3 的路径只有 0 → 1 → 2，边数为 2。

因此输出 2。

数据范围

• $1 \le N \le 2 \times 10^5$
• $1 \le K \le 10^6$
• $0 \le z \le 10^6$

算法分析

此题是典型的树上路径问题，要求权值和恰好为 $K$ 且边数最少。由于 $N$ 较大（$2 \times 10^5$），$K$ 也较大（$10^6$），需要采用高效算法。

思路

可以使用点分治（树分治）解决：

1. 每次找到当前子树的重心作为根。
2. 对于当前重心，计算所有经过该重心的路径，检查是否有权值和为 $K$ 的路径，并更新最少边数。
3. 递归处理重心的各个子树。

在计算经过重心的路径时，需要记录从重心到各个点的距离（权值和）以及边数，并用一个数组（或哈希表）记录某个距离对应的最少边数，以便快速查找互补值。

复杂度

点分治的复杂度为 $O(N \log N)$，配合合适的查找结构（如数组或哈希表）可以高效解决问题。

边界情况

• 如果没有任何路径权值和为 $K$，输出 $-1$。
• 注意权值可能为 0，路径可能只包含一条边。

提示

实现时需要注意：

1. 使用重心分解保证递归层数为 $O(\log N)$。
2. 使用数组记录距离时，数组大小至少为 $K$（因为距离可能超过 $K$，但超过 $K$ 的路径无需记录）。
3. 注意清零操作，避免不同子树之间的路径被错误合并。