a128. P_8_2 物流派送系統

Content

有一個物流派送系統，系統有n個工作站與n-1條輸送帶，工作站以0~n-1編號，其中0號站是進貨站，所有物品都是由0號站進入系統然後經過輸送帶配送到某個站。每個輸送帶都是單向的從某個站a把物品送到站b，輸送的時間是w(a,b)。

已知由進貨站可以經由輸送帶直接或間接轉送到達任何其他站，請計算下列兩者
(1). 由進貨站到達運送時間最長的站需要多少時間
(2). 由進貨站需要最多次轉運的需要經過幾次輸送帶。
舉例來說，如右圖，有5個站以4條輸送帶連接，假設每條輸送帶的運送時間如圖上標示。需要最長運送的時間是3號站(2+4=6)，最多需要經過的輸送帶是兩次(2號站與3號站)。

Input

第一行是正整數n，n>1，接下來有n-1行是輸送帶的資料，第i行2個整數x與w，代表此輸送帶連接x與i，輸送的時間是w。n不超過1e5，每條輸送帶的輸送時間是不超過1000的正整數。

Output

第一行輸出最長的運送總時間，第二行輸出最多經過幾次輸送帶。第一行與第二行的答案不一定是同一個站，除了輸送帶以外的時間均忽略不記。

Sample Input #1

Sample Output #1

6
2

Sample Input #2

Sample Output #2

9
4

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (20%): 1.0s , <1K
公開測資點#1 (20%): 1.0s , <1K
公開測資點#2 (20%): 1.0s , <1M
公開測資點#3 (20%): 1.0s , <1M
公開測資點#4 (20%): 1.0s , <1M

Hint ：

範例一：題目中的例子
範例二：時間最久的是0->1，時間是9；最多次的是0->2->3->5->4，共四次。
(測資1與2的n<=100且前一站的編號必然小於該站。)

Tags:

ch8

出處:

Prof.Wu [管理者： s710426(?0_o)//) ]

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