物流派送系統 (AP325 P-8-2)

有一個物流派送系統，系統有 \(n\) 個工作站與 \(n-1\) 條輸送帶，工作站以 \(0 \sim n-1\) 編號，其中 \(0\) 號站是進貨站，所有物品都是由 \(0\) 號站進入系統然後經過輸送帶配送到某個站。每個輸送帶都是單向的從某個站 \(a\) 把物品送到站 \(b\)，輸送的時間是 \(w(a,b)\)。已知由進貨站可以經由輸送帶直接或間接轉送到達任何其他站，請計算下列兩者：（1）由進貨站到達運送時間最長的站需要多少時間，以及（2）由進貨站需要最多次轉運的站需要經過幾次輸送帶。

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

輸入格式

第一行是正整數 \(n\)。接下來有 \(n-1\) 行是輸送帶的資料，\(i\) 由 \(1\) 到 \(n-1\)，第 \(i\) 行有 \(2\) 個整數 \(x\) 與 \(w\)，代表有一條輸送帶從 \(x\) 站送到 \(i\) 站，輸送的時間是 \(w\)。同一行的數字以一個空白隔開。

限制

• \(2 \le n \le 10^5\)。
• \(0 \le x \le n-1\)，\(x \ne i\)；每條輸送帶的輸送時間 \(w\) 是不超過 \(1000\) 的正整數。
• 保證由 \(0\) 號站可以到達每一個站。注意 \(x\) 的編號不一定比 \(i\) 小。

輸出格式

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

評分說明

每筆計分測資獨立計分，每筆 5 分，共 100 分；範例不計分。

範例輸入 1

5
0 5
4 1
4 4
0 2

範例輸出 1

6
2

範例輸入 2

6
0 9
0 1
2 1
5 3
3 2

範例輸出 2

9
4

範例說明

範例一是題目中的例子。範例二：時間最久的是 \(0 \to 1\)，時間是 \(9\)；經過最多次的是 \(0 \to 2 \to 3 \to 5 \to 4\)，共四次。

題目來源

本題出自中正大學吳邦一教授所著《AP325－從 APCS 實作題檢測三級到五級》（v1.5）第 8 章 P-8-2，第 275 頁；經作者同意於 AACPOJ 免費公開。教材下載：AP325 講義（Google Drive）；Python 版：AP325-Python（HackMD）。