a138. 107-01觀光景點 (Sights)

Content

打卡公司為了促進城市觀光，發展一個可推薦前往觀光（打卡）的App。該公司選定了 $N$ 個觀光（打卡）點，若遊客在任一觀光點打卡，該App就會預測遊客可能會有興趣的其他觀光點並推薦給該遊客。

為了能夠準確預測該推薦的觀光點，打卡公司設計了觀光景點相關性地圖（如右圖），圖上有 $N$ 個點，分別以 $V_1, V_2, V_3, …, V_N$ 代表觀光點，並精心挑選了 $N−1$ 組觀光點以線段相連並依據經驗給定 $R_{i,j}$ 值，以代表 $V_i$ 與 $V_j$ 的相關性。特別的是，該圖之任意兩點 $V_m$ 與 $V_n$ 一定有單一路徑 $p$ ，相互串連，而 $V_m$ 與 $V_n$ 的相關性就為該路徑上所有已知相關性的最小值 (即路徑上最小 $R_{i,j}$ 值)。以右圖為例 $V_1$ 與 $V_2$ 的相關性為 $ \min \{4, 3, 6\} = 3$。

請寫一個程式計算與任一觀光點 $V_k$ 相關性至少為 $q$ 的景點數量。

Input

輸入的第一行有三個以空白符號隔開的正整數 $N, V_k, q$。
接著 $N-1$ 行中，每一行有三個空白符號隔開的正整數分別代表 $i, j, R_{i,j}$。
保證 $1 ≤ i ≤ N$ 、 $1 ≤ j ≤ N$ 、 $q \leq 10^9$、 $R_{i,j} \leq 10^9$。

本題共有四個子題。

第一子題 $N = 4$，全對得18分。
第二子題 $N ≤ 10$，全對得36分。
第三子題 $N ≤ 50$，全對得29分。
第四子題 $N ≤ 5,000$，全對得17分。

Output

請輸出與觀光點 $V_k$ 相關性不低於 $q$ 的景點數量。

Sample Input #1

3 2 4
1 2 3
1 3 2

Sample Output #1

Sample Input #2

Sample Output #2

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (2%): 1.0s , <1M
公開測資點#1 (2%): 1.0s , <1K
公開測資點#2 (2%): 1.0s , <1K
公開測資點#3 (2%): 1.0s , <1K
公開測資點#4 (2%): 1.0s , <1K
公開測資點#5 (3%): 1.0s , <1K
公開測資點#6 (3%): 1.0s , <1M
公開測資點#7 (3%): 1.0s , <1M
公開測資點#8 (3%): 1.0s , <1M
公開測資點#9 (3%): 1.0s , <1M
公開測資點#10 (3%): 1.0s , <1M
公開測資點#11 (3%): 1.0s , <1K
公開測資點#12 (3%): 1.0s , <1K
公開測資點#13 (3%): 1.0s , <1K
公開測資點#14 (3%): 1.0s , <1K
公開測資點#15 (3%): 1.0s , <1K
公開測資點#16 (3%): 1.0s , <1K
公開測資點#17 (3%): 1.0s , <1K
公開測資點#18 (3%): 1.0s , <1M
公開測資點#19 (3%): 1.0s , <1M
公開測資點#20 (3%): 1.0s , <1M
公開測資點#21 (3%): 1.0s , <1K
公開測資點#22 (3%): 1.0s , <1K
公開測資點#23 (3%): 1.0s , <1K
公開測資點#24 (3%): 1.0s , <1K
公開測資點#25 (3%): 1.0s , <1K
公開測資點#26 (3%): 1.0s , <1K
公開測資點#27 (3%): 1.0s , <1K
公開測資點#28 (3%): 1.0s , <1M
公開測資點#29 (3%): 1.0s , <1M
公開測資點#30 (3%): 1.0s , <1M
公開測資點#31 (3%): 1.0s , <1M
公開測資點#32 (3%): 1.0s , <1M
公開測資點#33 (3%): 1.0s , <1M
公開測資點#34 (3%): 1.0s , <1M

Hint ：

Tags:

出處:

107全國學科能力競賽 [管理者： s710426(?0_o)//) ]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」