樹上的推銷員 (AP325 P-8-1)

有一個推銷員要走訪 \(n\) 個城市並在結束後回到出發的城市。這些城市以 \(n-1\) 條道路連接，每條道路連接兩個不同的城市並且雙向可以通行，而且已知每一個城市都可以到達，不會有到達不了的狀況。輸入道路的資料，請你找出一個長度最短的城市走訪順序，因為這樣的順序很多，你必須輸出字典順序最小的那一個。字典順序是用來比較兩個序列的先後順序，其方法是由前往後找到第一個不相同的位置，該元素比較小的序列就是順序比較小，如同在英文字典中單字的順序一般。例如 \((0,2,3,1) < (0,3,1,2)\)，又 \((0,3,2,1) < (1,0,2,3)\)。

舉例來說，如下圖，有 \(5\) 個城市以 \(4\) 條道路連接，假設每條道路的長度都是 \(1\)。字典順序最小的最短拜訪順序是 \((0,1,0,4,2,4,3,4,0)\)。

輸入格式

第一行是正整數 \(n\)，代表城市的數量，城市是以 \(0 \sim n-1\) 編號。接下來有 \(n-1\) 行是道路的資料，每行三個整數 \(a\)、\(b\) 與 \(w\)，代表此道路連接城市 \(a\) 與 \(b\)，道路的長度是 \(w\)。同一行的數字以一個空白隔開。

限制

• \(1 \le n \le 50000\)。
• \(0 \le a, b \le n-1\)，\(a \ne b\)；每條道路長度 \(w\) 是不超過 \(100\) 的正整數。
• 保證任兩個城市之間都可以經由道路互相到達。

輸出格式

第一行輸出最短的旅行距離，第二行輸出拜訪順序（從 \(0\) 號城市出發、回到 \(0\) 號城市，共 \(2n-1\) 個數字），相鄰的數字之間要以一個空白隔開。

評分說明

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

範例輸入 1

5
1 0 1
0 4 1
2 4 1
4 3 1

範例輸出 1

8
0 1 0 4 2 4 3 4 0

範例輸入 2

3
1 2 5
0 2 3

範例輸出 2

16
0 2 1 2 0

題目來源

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