c057. 3. 石窟探險

Content

有一組探險隊要去一個樹狀結構的石窟內探險，該石窟內有 $n$ 個石室，第 $i$ 個石室有一個編號 $a_i$，若 $a_i$ 為偶數則會有 $2$ 條分支(左分支和右分支)，若 $a_i$ 為奇數則有 $3$ 條分支(左分支、中分支和右分支)。

探險隊想要紀錄這個石窟的結構，每次只要第一次走到一個新的石室，就會將該石室的編號記錄在紙上，並由左到右依序走訪該石室的分支們，若走到一條死路則會在紙上紀錄一個數字 $0$，若該石室已經走完所有分支則退回到上一個石室，走訪完整個石窟後在紙上得到上一個數字序列。

探險隊回到基地後忘記計算了這個石窟內所有相鄰的石室編號相差取絕對值的總和，請幫助探險隊從紙上的序列推算出該數值。

Input

輸入一個整數個數不超過 $10^6$ 的整數序列，石室的編號不超過 $10^5$，保證所有編號不重複，並保證造出來的樹深度不超過 $40$。

子題配分
(20%): 石室數量最多不超過 $20$ 個，編號均為偶數
(20%): 石室數量最多不超過 $10^3$ 個
(60%): 石室最大深度不超過40層，而且編號和石室編號不超過 $10^5$，答案可能會超過 $2^{31}$。

Output

輸出一個整數代表這個石窟內所有相鄰的石室編號相差取絕對值的總和，答案大小有可能會超過 $2^{31}$。

Sample Input #1

2 6 0 8 14 0 0 0 10 0 4 0 0

Sample Output #1

Sample Input #2

5 2 10 0 0 0 8 0 0 17 0 0 0

Sample Output #2

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (5%): 1.0s , <1K
公開測資點#1 (5%): 1.0s , <1K
公開測資點#2 (5%): 1.0s , <1K
公開測資點#3 (5%): 1.0s , <1K
公開測資點#4 (5%): 1.0s , <1M
公開測資點#5 (5%): 1.0s , <1M
公開測資點#6 (5%): 1.0s , <1M
公開測資點#7 (5%): 1.0s , <1M
公開測資點#8 (5%): 1.0s , <1M
公開測資點#9 (5%): 1.0s , <1M
公開測資點#10 (5%): 1.0s , <1M
公開測資點#11 (5%): 1.0s , <1M
公開測資點#12 (5%): 1.0s , <1M
公開測資點#13 (5%): 1.0s , <1M
公開測資點#14 (5%): 1.0s , <1M
公開測資點#15 (5%): 1.0s , <1M
公開測資點#16 (5%): 1.0s , <1M
公開測資點#17 (5%): 1.0s , <1M
公開測資點#18 (5%): 1.0s , <1M
公開測資點#19 (5%): 1.0s , <1M

Hint ：

範例測資一

|2 - 6| + |6 - 8| + |8 - 14| + |2 - 10| + |10 - 4| = 26

範例測資二

|5 - 2| + |2 - 10| + |5 - 8| + |5 - 17| = 26

Tags:

APCS dfs 樹

出處:

2022年10月 APCS 演算法海牛 [管理者： ktlai (K．我已霸榜．Tlai) ]

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