40 . 樹上最小著色問題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (36/36)

Submission's AC Ratio

63.8% (81/127)

Tags

ioicamp ioicamp-2024

Description

你聽過圖著色問題嗎？這是一個著名的 NP-complete 問題，這個經典題目是這樣的，給你一張圖，你必須要將圖上的每個節點塗上顏色，問你至少要有幾種顏色才能讓圖上所有距離為 1 的節點都是不同顏色。

現在我們要問一個類似的問題：給你一棵樹，你必須要將樹上的每個節點塗上顏色，問你至少要有幾種顏色才能讓樹上所有距離為 2 的節點都是不同顏色。

Input Format

輸入第一行包含一個正整數 N，代表點的數量。

接下來的 N−1 行，第 i 行包含兩個正整數 ai, bi，代表節點 ai 和節點 bi 之間有一條邊。

  • 1≤N≤40
  • 1≤ai,bi≤N

Output Format

請輸出能將整棵樹按照規則塗色的最小顏色數量。

Sample Input 1

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

Sample Output 2

3

Hints

Problem Source

IOICamp 2024 Day4 pG

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~13 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2
1 1000 262144 65536 1 2
2 1000 262144 65536 2
3 1000 262144 65536 2
4 1000 262144 65536 2
5 1000 262144 65536 2
6 1000 262144 65536 2
7 1000 262144 65536 2
8 1000 262144 65536 2
9 1000 262144 65536 2
10 1000 262144 65536 2
11 1000 262144 65536 2
12 1000 262144 65536 2
13 1000 262144 65536 2
Submit
Back to Top