TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

Description

殿壬是個天才兒童,他在一個月大的時候就學會數數、六個月大的時候就學會乘法跟除法、一歲時學會寫程式、一歲又六個月時養了可愛的拉不拉多、一歲又十個月時養了可愛的貓咪、兩歲時發明了「吃餅乾」的遊戲,而現在要講的,是殿壬四點二個月大的故事。

這一天他從百科全書看到了蝴蝶效應:
「蝴蝶效應 (Butterfly effect) 是指在一個動態系統中,初始條件的微小變化,將能帶動整個系統長期且巨大的連鎖反應,是一種混沌的現象。」
摘錄自自由的百科全書。

原來蝴蝶是混沌的!然後他開始研究蝴蝶,接著殿壬只要念得快了,蝴蝶蝴蝶皮蝶皮球,其實蝴蝶跟皮球也差不多。

踢皮球有很多益處,可以大事化小,小事化無,補充運動量,強身健體。

所以接下來介紹一個蝴蝶公司裡面的踢皮球制度:

蝴蝶公司的階級可以用一棵 $N$ 個點的有根樹來表示,每一個點可以對應到一隻蝴蝶。

其中 $1$ 號點是根結點,除了 $1$ 號點之外每個點 $i$ 都有父節點 $p_i$
每個點的父節點對應到上司,每個點的子樹則對應到下屬,因此樹上的所有點都是根結點的下屬。

每隻蝴蝶都有著一個 $1$ 到 $N$ 的帳號,而且互不相同。

踢皮球是這樣玩的:

首先球會出現在帳號為 $1$ 的蝴蝶手上
當一隻蝴蝶接到一個皮球之後,他就會把皮球丟到他帳號的下一號 ( $1$ 號丟給 $2$ 號, ..., $N$ 號丟給 $1$ 號)。
如果一隻蝴蝶 $A$ 選擇將皮球丟給牠的下屬 $B$ ,則將會產生怒氣值,怒氣值的大小是樹上 $A$ 點到 $B$ 點的距離,每條邊的距離都是 $1$。

可以發現,如果大家都不太想要生氣,那帳號的分配十分重要。
怒氣值總和則是一種度量怒氣的方法,其值為將皮球從 $1$ 號蝴蝶踢回 $1$ 號蝴蝶過程的所有怒氣值和。

殿壬預測到到三個年多後,他將會抓到一群蝴蝶的公司,剛好有 $N$ 隻,他也預測好了每隻蝴蝶的上司是誰。
所以唯一的問題就是,要怎麼幫蝴蝶分配帳號,才可以建立怒氣值總和最小的踢皮球系統?

Input Format

輸入第一行有一個正整數 $N$ ,代表蝴蝶的數量。
輸入第二行有 $N - 1$ 個正整數依序代表 $p_2, p_3, ..., p_N$ 。

  • $2 \leq N \leq 300000$
  • $1 \leq p_i < i$

Output Format

輸出一共有兩行。
第一行共有一個數字表示最小的怒氣值總和。
第二行共有 $N$ 個數字,第 $i$ 個數字代表編號為 $ i$ 的蝴蝶分配到的帳號,若有多組解可以輸出任意一種。

Sample Input

Sample Input 1:
4
1 1 1
Sample Input 2:
3
1 2

Sample Output

Sample Output 1:
1
1 2 3 4
Sample Output 2:
2
3 2 1

Hints

範例測試資料二中,其中一種最佳的分配方法為 $(3, 2, 1)$ ,每段怒氣值為分別為:$1 \to 2$ 怒氣值為 0 、$2 \to 3$ 怒氣值為 0 、 $3 \to 1$ 怒氣值為 2 ,因此總怒氣值為 2 ,且沒有其他分配方法可以達到更小的怒氣值。

此外 $(1, 2, 3)$ 也是一組合法的解。

Problem Source

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 262144 262144
1 1000 262144 262144
2 1000 262144 262144
3 1000 262144 262144
4 1000 262144 262144
5 1000 262144 262144
6 1000 262144 262144
7 1000 262144 262144
8 1000 262144 262144
9 1000 262144 262144
10 1000 262144 262144
11 1000 262144 262144
12 1000 262144 262144
13 1000 262144 262144
14 1000 262144 262144
15 1000 262144 262144
16 1000 262144 262144
17 1000 262144 262144
18 1000 262144 262144
19 1000 262144 262144
20 1000 262144 262144
21 1000 262144 262144
22 1000 262144 262144
23 1000 262144 262144
24 1000 262144 262144
25 1000 262144 262144
26 1000 262144 262144
27 1000 262144 262144
28 1000 262144 262144
29 1000 262144 262144
30 1000 262144 262144
31 1000 262144 262144
32 1000 262144 262144
33 1000 262144 262144
34 1000 262144 262144
35 1000 262144 262144
36 1000 262144 262144
37 1000 262144 262144
38 1000 262144 262144
39 1000 262144 262144
40 1000 262144 262144
41 1000 262144 262144
42 1000 262144 262144