TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

81.8% (9/11)

Submission's AC Ratio

32.7% (18/55)

Tags

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:
1
5
1
1
2
2

#2:
2
5
1
1
2
2

Sample Output 1

#1:
2

#2:
1
1
1
2
2

Hints

Problem Source

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 131072 262144 1
1 2000 131072 262144 2
2 2000 131072 262144 3
3 2000 131072 262144 4
4 2000 131072 262144 5
5 2000 131072 262144 6
6 2000 131072 262144 7
7 2000 131072 262144 8
8 2000 131072 262144 9
9 2000 131072 262144 10