巡逻

题目描述

在边境森林中，分布着若干个重要的哨站，所有的哨站之间通过隐秘小径相连，构成了一个天然的巡逻网络。这张网络的结构恰好形成了一棵树。为了防止敌人渗透，小蓝每天需要执行固定长度为\(k\)的巡逻任务。

每次巡逻从一个哨站出发，经过不重复地恰好\(k\)条道路，最终到达另一个哨站。每条道路都有一定的危险值，巡逻路径上所有道路的危险值的总和代表该次巡逻的风险。两条巡逻路径不同当且仅当它们的起点或终点不同。

现在，指挥官希望知道，所有可能的长度为\(k\)的巡逻路线的风险之和是多少。

输入格式

• 第一行包含两个正整数\(n\)和\(k\)，分别表示树的节点数和巡逻的道路数。
• 接下来\(n-1\)行，每行包含三个整数\(u_i, v_i, w_i\)，表示节点\(u_i\)和节点\(v_i\)之间有一条危险值为\(w_i\)的边。

输出格式

输出一行包含一个整数，表示所有可能长度为\(k\)的巡逻路径的风险之和。

输入输出样例

输入样例 #1

7 2
1 2 3
2 4 5
1 3 7
3 5 3
3 6 4
6 7 2

输出样例 #1

104

说明

样例解释：

所有可能的路径及其风险值如下：

-\(1 \rightarrow 2 \rightarrow 4:\)风险值\(=3 + 5 = 8 -\)2 \rightarrow 1 \rightarrow 3:\(风险值\)=3 + 7 = 10 -\(1 \rightarrow 3 \rightarrow 5:\)风险值\(=7 + 3 = 10 -\)1 \rightarrow 3 \rightarrow 6:\(风险值\)=7 + 4 = 11 -\(5 \rightarrow 3 \rightarrow 6:\)风险值\(=3 + 4 = 7 -\)3 \rightarrow 6 \rightarrow 7:\(风险值\)=4 + 2 = 6

以上路径反过来也是合法的，所以总共有14条不同的路径，风险之和为104。

数据范围与约定

对于所有数据，1 \leq n \leq 10^5，1 \leq k \leq n，1 \leq u_i, v_i \leq n，1 \leq w_i \leq 10^6。