打卡公司為了促進城市觀光,發展一個可推薦前往觀光(打卡)的App。該公司選定了 N 個觀光(打卡)點,若遊客在任一觀光點打卡,該App就會預測遊客可能會有興趣的其他觀光點並推薦給該遊客。
為了能夠準確預測該推薦的觀光點,打卡公司設計了觀光景點相關性地圖(如下圖),圖上有 N 個點,分別以 V1, V2, V3, …, VN 代表觀光點,並精心挑選了 N−1 組觀光點以線段相連並依據經驗給定 Ri,j 值,以代表 Vi 與 Vj 的相關性。特別的是,該圖之任意兩點 Vm 與 Vn 一定有單一路徑 p ,相互串連,而Vm 與 Vn 的相關性就為該路徑上所有已知相關性的最小值 (即路徑上最小Ri,j值)。以下圖為例 V1 與 V2的相關性為 min {4, 3, 6} = 3。
請寫一個程式計算與任一觀光點 Vk 相關性至少為 q 的景點數量。
輸入的第一行有三個以空白符號隔開的正整數 N, Vk, q。接著 N-1 行中,每一行有三個空白符號隔開的正整數分別代表 i, j, Ri,j。保證1 ≤ i ≤ N、1 ≤ j ≤ N、q≤109、Ri,j ≤ 109。
請輸出與觀光點 Vk 相關性不低於 q 的景點數量。
3 2 4 1 2 3 1 3 2
0
6 4 6 4 2 10 3 6 3 5 3 8 2 3 6 1 6 4
3
本題共有四個子題。第一子題N = 4,全對得18分。第二子題N ≤ 10,全對得36分。第三子題 N ≤ 50,全對得29分。第四子題 N ≤ 5,000,全對得17分。
ID | User | Problem | Subject | Hit | Post Date |
38423 | qerpzzea@gma ... (賽希爾 cecill(陳宥穎)) | c812 | 249 | 2023-11-21 20:24 | |
24787 | kevin2002062 ... (欣倫李) | c812 | 1201 | 2021-03-25 18:09 |