A. Colorful Tree

Codeforces

IDCF10048A

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

It is an interesting problem in graph theory called “graph coloring”. _In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called “colors” to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the same color; this is called a vertex coloring._ (from Wikipedia) The smallest number of colors needed to color a graph is called its chromatic number. #cf_span(class=[tex-font-style-sc], body=[the student asks]): I wonder if this problem is easy on trees. #cf_span(class=[tex-font-style-sc], body=[the teacher explains]): Well, two colors is enough for trees. But the critical thinking student thought he should better check that. He thought it is too simple to be true. Note: the tree is a connected graph with no cycles. The first line contains the number of test cases _T_ (0 ≤ T ≤ 20). The first line of each test case contains the number of vertices in the tree, _n_ (1 ≤ n ≤ 105). The following n - 1 lines contains numbers _a_ and _b_ (1 ≤ a < b ≤ n), meaning that vertices _a_ and _b_ are connected. For each test case output one line containing “_Case #tc: num_”, where _tc_ is the number of the test case (starting from 1) and _num_ is the chromatic number of the given tree. ## Input The first line contains the number of test cases _T_ (0 ≤ T ≤ 20). The first line of each test case contains the number of vertices in the tree, _n_ (1 ≤ n ≤ 105). The following n - 1 lines contains numbers _a_ and _b_ (1 ≤ a < b ≤ n), meaning that vertices _a_ and _b_ are connected. ## Output For each test case output one line containing “_Case #tc: num_”, where _tc_ is the number of the test case (starting from 1) and _num_ is the chromatic number of the given tree. [samples]

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case $ k \in \{1, \dots, T\} $: - Let $ G_k = (V_k, E_k) $ be a tree with $ n_k $ vertices, where $ V_k = \{1, 2, \dots, n_k\} $. - $ E_k \subseteq \binom{V_k}{2} $ is the edge set, given as pairs $ (a, b) $ with $ 1 \leq a < b \leq n_k $. **Constraints** 1. $ 0 \leq T \leq 20 $ 2. For each test case $ k $: - $ 1 \leq n_k \leq 10^5 $ - $ |E_k| = n_k - 1 $ - $ G_k $ is connected and acyclic (i.e., a tree). **Objective** For each test case $ k $, compute the chromatic number $ \chi(G_k) $ of the tree $ G_k $.

API Response (JSON)

{
  "problem": {
    "name": "A. Colorful Tree",
    "description": {
      "content": "It is an interesting problem in graph theory called “graph coloring”. _In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called “colors”",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10048A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "It is an interesting problem in graph theory called “graph coloring”.\n\n_In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called “colors”...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ G_k = (V_k, E_k) $ be a tree with $ n_k $ vertices, where $ V_k = \\{1,...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments