1800 . Color On a Tree
TopCoder
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
1
5
1
1
2
2
#2:
2
5
1
1
2
2
Sample Output 1
#1:
2
#2:
1
1
1
2
2
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 |