1647 . 捕魚方案計數

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

柊 四千
あぅあぅ～

User's AC Ratio

84.6% (11/13)

Submission's AC Ratio

24.2% (38/157)

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 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
Submit
Back to Top