TopCoder

Thumb
柊 四千
あぅあぅ~

User's AC Ratio

66.7% (2/3)

Submission's AC Ratio

43.8% (7/16)

Tags

SSC

Description


在遙遠的彼方,有一群列島,據說在那些島嶼之間的水路上,可以捕獲許許多多在其他地方補不到的鮮魚。

也因為如此,儘管路途遙遠,每年仍有許多漁夫們開著象徵榮耀的漁船遠征該海域,希望能夠捕獲世上最好的鮮魚。


這群列島包含 N 座獨立的島嶼,之間有 N-1 條海路連接著這些島嶼,使得這 N 座島嶼的任何一座都可以藉由這些海路到達其他N-1座島嶼。

對於每一條水路,有一個對應的「漁獲價值」,而這個「漁獲價值」越大代表你可以在經過這條水路時能夠捕獲越好的魚;

當然,這個值也可能是負的,例如你可能會不小心捕到鯊魚,然後牠會把你漁網裡的魚都吃光之類的。


現在,你可以挑選兩座不同的島嶼,並從其中一座前往另一座,而你的船上有一張牢不可破的漁網,在之間(唯一的)的路途中,

你可以選擇你何時要放下漁網以及何時要收起漁網。當然,你會希望你最後捕獲總「漁獲價值」和越高的漁獲越好。

而現在你希望知道的是,在你的判斷不出錯(都選擇最好的放下和收起魚網的時間點)的前提下,總共有幾對島嶼 Ii, Ij 滿足最大「漁獲價值」和可以大於等於 K。


為了簡化題目,我們規定在捕魚的過程中,對於放下網時每一條經過的水路,只能選擇全捕。

並且,一旦你將放下的漁網收起後,就再也不能放下漁網了。


當然,你也可以相信你的漁網足夠大,可以容納無窮多的魚在其中。

Input Format


本題輸入的測試檔只有單筆測試資料,第一行有兩個整數 N, K,代表這群列島共有 N 個島嶼。

接下來有 N-1 行,每一行有三個整數 Ai, Bi 和 Ci,代表該條水路連接編號 Ai 的島嶼和編號 Bi 的島嶼,並且漁獲價值為 Ci

對於所有測試資料,保證1 ≤ N ≤ 200000,1 ≤ Ai, Bi ≤ N,-106 ≤ Ci ≤ 106

Output Format


請輸出一個整數 P,代表共有幾對島嶼可以使你獲得價值大於等於 K 的魚獲。

Sample Input

4 2
1 2 -1
2 3 2
2 4 1

Sample Output

3

Hints

Problem Source

原TIOJ1647 / Skyly & Shik Contest II (Problem H)

Subtasks

For Testdata: 0 ~ 0, Score: 9
For Testdata: 1 ~ 1, Score: 9
For Testdata: 2 ~ 2, Score: 9
For Testdata: 3 ~ 3, Score: 9
For Testdata: 4 ~ 4, Score: 9
For Testdata: 5 ~ 5, Score: 9
For Testdata: 6 ~ 6, Score: 9
For Testdata: 7 ~ 7, Score: 9
For Testdata: 8 ~ 8, Score: 9
For Testdata: 9 ~ 9, Score: 9
For Testdata: 10 ~ 10, Score: 10
No. Time Limit (ms) Memory Limit (KiB)
0 5000 65536
1 5000 65536
2 5000 65536
3 5000 65536
4 5000 65536
5 5000 65536
6 5000 65536
7 5000 65536
8 5000 65536
9 5000 65536
10 5000 65536