TopCoder

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

User's AC Ratio

100.0% (7/7)

Submission's AC Ratio

60.0% (9/15)

Description

有一棵樹,你要為它的邊塗色(這世界上有無限多種顏色),並要符合以下規則:
1. 任一個節點$i$,最多只有一條邊(有連到$i$)可以找到另一條邊(也有連到$i$)跟其顏色相同
2. 兩條邊若顏色相同,則他們之間的那條path皆為同樣顏色(與這兩邊相同)

最小化:從根到所有點的諸多path中,「經過最多相異顏色的那條」的顏色數量。

Input Format

一開始是一個數字$X$,代表回答類型:$1$或者是$2$,
接下來為一個數字$N$,代表該顆樹有幾個節點($N \leq 300000$),
再來有$N-1$個數字,第$i$個數字代表節點$i+1$的父節點為何者($1 \to i$)

50%的測資為回答類型1
50%的測資為回答類型2
20%的測資為一條鏈

Output Format

若回答類型是1,輸出一個數字代表整顆樹的所求,
若回答類型是2,對於那$N-1$個數字,輸出到目前為止,這棵尚未完成的樹的所求。最後再輸出一行整棵樹的所求。

Sample Input

#1:
1
5
1
1
2
2

#2:
2
5
1
1
2
2

Sample Output

#1:
2

#2:
1
1
1
2
2

Hints

Problem Source

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 2000 131072 262144
1 2000 131072 262144
2 2000 131072 262144
3 2000 131072 262144
4 2000 131072 262144
5 2000 131072 262144
6 2000 131072 262144
7 2000 131072 262144
8 2000 131072 262144
9 2000 131072 262144