TopCoder

柊 四千
あぅあぅ~

User's AC Ratio

91.7% (11/12)

Submission's AC Ratio

27.0% (38/141)

Tags

SSC

Description


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

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


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

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

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


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

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

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


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

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


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

Input Format


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

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

對於所有測試資料,保證$1 \leq N \leq 200000$,$1 \leq A_i, B_i \leq N$,$-10^ 6 \leq C_i \leq 10^ 6$。

Output Format


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

Sample Input 1

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

Sample Output 1

3

Hints

Added $\LaTeX$ by Seanliu on 20201021

Problem Source

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

Subtasks

No. Testdata Range Score
1 0 9
2 1 9
3 2 9
4 3 9
5 4 9
6 5 9
7 6 9
8 7 9
9 8 9
10 9 9
11 10 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 65536 262144 1
1 5000 65536 262144 2
2 5000 65536 262144 3
3 5000 65536 262144 4
4 5000 65536 262144 5
5 5000 65536 262144 6
6 5000 65536 262144 7
7 5000 65536 262144 8
8 5000 65536 262144 9
9 5000 65536 262144 10
10 5000 65536 262144 11