d108. P_8_2 物流派送系統

Content

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

已知由進貨站可以經由輸送帶直接或間接轉送到達任何其他站，請計算下列兩者

舉例來說，如右圖，有 $5$ 個站以 $4$ 條輸送帶連接，假設每條輸送帶的運送時間如圖上標示。需要最長運送的時間是 $3$ 號站 $(2+4=6)$，最多需要經過的輸送帶是兩次( $2$號站與 $3$ 號站)。

Input

第一行是正整數 $n$，$n>1$，

接下來有 $n-1$ 行是輸送帶的資料，第 $i$ 行 $2$ 個整數 $x$ 與 $w$，代表此輸送帶連接 $x$ 與 $i$，輸送的時間是 $w$，$i = 1 \sim (n-1)$。

$n$不超過 $10^5$，每條輸送帶的輸送時間是不超過 $1000$ 的正整數。

Output

第一行輸出最長的運送總時間，第二行輸出最多經過幾次輸送帶。

第一行與第二行的答案不一定是同一個站，除了輸送帶以外的時間均忽略不記。

Sample Input #1

Sample Output #1

6
2

Sample Input #2

Sample Output #2

9
4

測資資訊：

記憶體限制： 256 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 \rightarrow 1$，時間是 $9$ ；最多次的是 $0 \rightarrow 2 \rightarrow 3 \rightarrow 5 \rightarrow 4$，共四次。

(測資1與2的 $n \le 100$ 且前一站的編號必然小於該站。)

Tags:

ch8

出處:

Prof. Wu [管理者：

ktlai (K．我已霸榜．Tlai)

]

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