Problem
カイマンは、街の見知らぬ場所にいるという珍しい夢を見ます。このエリアはツリー グラフとして表すことができます。頂点は交差点、エッジはこれらの交差点を接続する双方向道路です。交差点は全部で n つあり、それぞれに 0 から n-1 までの番号が付いています。
しかし、この夢の中ではすべてがそれほど悪いわけではありません。なぜなら、番号 u と v の交差点間のすべての道路に C
u,v 団子があるからです。カイマンは団子が大好きなので、たくさん食べたいのですが、問題があり、交差点をk回以上訪れると、邪悪な団子モンスターに襲われます。
これは夢ですが、道に沿って何度も歩くことを妨げるものは何もありませんが、各道にある団子は一度しか食べることができません。また、ケイマンは道路上で止まりません。つまり、ある交差点から別の交差点へ移動を始めたら、必ず次の交差点まで
進んでしまうのです。
夢の始まりで、カイマンは岐路 0 に立っていました。邪悪な餃子モンスターに攻撃されずに食べられる餃子の最大数を決めるのを手伝ってください。
入力:
最初の行には、2 つの整数 n と k (3 ≤ n ≤ 10
5; 1≤ k ≤ 10
5) が含まれています。交差点の数と各交差点への最大訪問回数
次の n - 1 行には、3 つの整数 u、v および C
u,v (0 ≤ u, v ≤ n - 1; 0 ≤ C
u,v< /sub) が含まれます。 > ≤ 10000)、数字 u と v の交差点が Cu,v 団子のある道路で結ばれていることを意味します。
交差点や道路が樹木を形成していることが
保証されています。
出力:
カイマンが食べられる餃子の最大数を 1 つの整数で出力します。
例:
<本体>
| 入力 |
出力 |
9 3
0 1 1
0 2 1
1 3 2
1 4 2
1 5 2
2 6 3
2 7 3
2 8 3
| 15 |
9 5
0 1 1
0 2 1
1 3 2
1 4 2
1 5 2
2 6 3
2 7 3
2 8 3
| 17 |
11 6
1 0 7932
1952年21日
3 2 2227
4 0 9112
5 4 6067
6 0 6786
7 6 3883
8 4 7137
9 1 2796
10 5 6200
| 54092 |
説明:
最初の例では、次の順序で交差点にアクセスする必要があります: 0, 1, 5, 1, 3, 1, 0, 2, 6,&thinsp ;2、 7、?2、?8。そして合計1+2+2+1+3+3+3=15個の餃子を
食べることになります。
どの交差点も 3 回以上訪問しないことに注意してください。