40 . 樹上最小著色問題
TopCoder
Tags
Description
你聽過圖著色問題嗎？這是一個著名的 NP-complete 問題，這個經典題目是這樣的，給你一張圖，你必須要將圖上的每個節點塗上顏色，問你至少要有幾種顏色才能讓圖上所有距離為 $1$ 的節點都是不同顏色。
現在我們要問一個類似的問題：給你一棵樹，你必須要將樹上的每個節點塗上顏色，問你至少要有幾種顏色才能讓樹上所有距離為 $2$ 的節點都是不同顏色。
Input Format
輸入第一行包含一個正整數 $N$，代表點的數量。
接下來的 $N-1$ 行，第 $i$ 行包含兩個正整數 $a_i$, $b_i$，代表節點 $a_i$ 和節點 $b_i$ 之間有一條邊。
- $1 \le N \le 40$
- $1 \le a_i, b_i \le N$
Output Format
請輸出能將整棵樹按照規則塗色的最小顏色數量。
Sample Input 1
5
1 2
2 3
3 4
4 5
1 2
2 3
3 4
4 5
Sample Output 1
2
Sample Input 2
5
1 2
2 3
2 4
1 5
1 2
2 3
2 4
1 5
Sample Output 2
3
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資。 | 0 |
| 2 | 0~13 | 無特別限制。 | 100 |