P12874 [蓝桥杯 2025 国 Python A] 巡逻

建议 Python 用户选择 PyPy3 提交本题。

边境森林中分布着若干重要的哨站，所有哨站之间由隐秘小径相连，形成一张天然的巡逻网络。这张网络的结构恰好是一棵树。为了防止敌人渗透，小蓝每天需要执行固定长度为 $k$ 的巡逻任务。每次巡逻从一个哨站出发，经过不重复地恰好 $k$ 条道路，最终到达另一个哨站。每条道路都有一定的危险值，巡逻路径上危险值的和代表该次巡逻时的风险。两次巡逻路径不相同当且仅当它们的起点不同或终点不同。 现在指挥官希望知道，所有可能的长度为 $k$ 的巡逻路线的风险之和是多少？

输入的第一行包含两个正整数 $n, k$ ，用一个空格分隔。 接下来 $n-1$ 行，每行包含三个正整数 $u_i, v_i, w_i$ ，相邻整数之间使用一个空格分隔。表示结点 $u_i$ 和结点 $v_i$ 之间有一条危险值为 $w_i$ 边。

输出一行包含一个整数表示答案。

**【样例说明】** 所有可能的路径及其风险值如下： - $1 \rightarrow 2 \rightarrow 4: 8$ - $2 \rightarrow 1 \rightarrow 3: 10$ - $1 \rightarrow 3 \rightarrow 5: 10$ - $1 \rightarrow 3 \rightarrow 6: 11$ - $5 \rightarrow 3 \rightarrow 6: 7$ - $3 \rightarrow 6 \rightarrow 7: 6$ 以上路径反过来也是合法的，所以总共有 14 条不同的路径，风险之和为 104。 **【评测用例规模与约定】** 对于 40% 的评测用例，$1 \leq n \leq 500$； 对于所有评测用例，$1 \leq n \leq 5000$，$1 \leq k \leq n$，$1 \leq u_i, v_i \leq n$，$1 \leq w_i \leq 10^6$。