B. 2Trees

Codeforces

IDCF10125B

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

You are given two trees with the same number of leaves L, your task is to merge the two trees' leaves in a way that ensures the following: Note that by merging two leaves a and b, the resulting node will have both edges of a and b. The first line of input contains one integer N (3 ≤ N ≤ 105), the number of nodes in the first tree. Then follows N - 1 lines, the ith line contains two integers u and v (1 ≤ u, v ≤ N), the indices of the nodes connected by the ith edge in the first tree. The next line contains an integer M (3 ≤ M ≤ 105), the number of nodes in the second tree. Then follows M - 1 lines, the ith line contains two integers u and v (1 ≤ u, v ≤ M), the indices of the nodes connected by the ith edge in the second tree. It is guaranteed that the two trees will have the same number of leaves L. On a single line print the number of colors needed to color the resulting graph. Followed by L lines, the ith line of them contains two integers u and v (1 ≤ u ≤ N)(1 ≤ v ≤ M), the indices of the leaves to be merged, where u is a leaf in the first tree, and v is a leaf in the second tree. If there’s more than one possible solution, print any of them. In the first sample, the two trees can be illustrated as follows: After merging node 2 from first tree with node 1 from the second tree, and node 3 from the first tree with node 2 from the second tree, the resulting graph is illustrated in the figure below: The minimum number of colors required to satisfy the problem constraints is 2. ## Input The first line of input contains one integer N (3 ≤ N ≤ 105), the number of nodes in the first tree.Then follows N - 1 lines, the ith line contains two integers u and v (1 ≤ u, v ≤ N), the indices of the nodes connected by the ith edge in the first tree.The next line contains an integer M (3 ≤ M ≤ 105), the number of nodes in the second tree.Then follows M - 1 lines, the ith line contains two integers u and v (1 ≤ u, v ≤ M), the indices of the nodes connected by the ith edge in the second tree.It is guaranteed that the two trees will have the same number of leaves L. ## Output On a single line print the number of colors needed to color the resulting graph.Followed by L lines, the ith line of them contains two integers u and v (1 ≤ u ≤ N)(1 ≤ v ≤ M), the indices of the leaves to be merged, where u is a leaf in the first tree, and v is a leaf in the second tree.If there’s more than one possible solution, print any of them. [samples] ## Note A tree of N nodes is a connected undirected graph with N - 1 edges. A node is a leaf if and only if it is connected to at most one other node. In the first sample, the two trees can be illustrated as follows: After merging node 2 from first tree with node 1 from the second tree, and node 3 from the first tree with node 2 from the second tree, the resulting graph is illustrated in the figure below: The minimum number of colors required to satisfy the problem constraints is 2.

**Definitions** Let $ T_1 = (V_1, E_1) $ and $ T_2 = (V_2, E_2) $ be two trees with $ |V_1| = N $, $ |V_2| = M $, and the same number of leaves $ L $. Let $ L_1 \subseteq V_1 $, $ L_2 \subseteq V_2 $ denote the sets of leaves of $ T_1 $ and $ T_2 $, respectively, with $ |L_1| = |L_2| = L $. **Constraints** 1. $ 3 \leq N, M \leq 10^5 $ 2. $ T_1 $ and $ T_2 $ are trees (connected, acyclic, undirected). 3. The merging operation identifies each leaf $ u \in L_1 $ with exactly one leaf $ v \in L_2 $, forming a bijection $ f: L_1 \to L_2 $. 4. The resulting graph $ G = (V, E) $ is formed by: - $ V = (V_1 \cup V_2) / \sim $, where $ u \sim f(u) $ for all $ u \in L_1 $, - $ E = E_1 \cup E_2 $. **Objective** 1. Compute the **minimum number of colors** required for a proper vertex coloring of $ G $. 2. Output a bijection $ f: L_1 \to L_2 $ specifying which leaves to merge. **Note**: The chromatic number of $ G $ depends on the structure of the merged graph; the goal is to minimize it over all possible bijections $ f $.

API Response (JSON)

{
  "problem": {
    "name": "B. 2Trees",
    "description": {
      "content": "You are given two trees with the same number of leaves L, your task is to merge the two trees' leaves in a way that ensures the following: Note that by merging two leaves a and b, the resulting node ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10125B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given two trees with the same number of leaves L, your task is to merge the two trees' leaves in a way that ensures the following:\n\nNote that by merging two leaves a and b, the resulting node ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T_1 = (V_1, E_1) $ and $ T_2 = (V_2, E_2) $ be two trees with $ |V_1| = N $, $ |V_2| = M $, and the same number of leaves $ L $.  \nLet $ L_1 \\subseteq V_1 $, $ L_2 \\subseteq V_...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments