C. Useful Decomposition

Codeforces

IDCF981C

Time1000ms

Memory256MB

Difficulty—

implementationtrees

English · Original

Chinese · Translation

Formal · Original

Ramesses knows a lot about problems involving trees (undirected connected graphs without cycles)! He created a new useful tree decomposition, but he does not know how to construct it, so he asked you for help! The decomposition is the splitting the edges of the tree in some simple paths in such a way that each two paths have at least one common vertex. Each edge of the tree should be in exactly one path. Help Remesses, find such a decomposition of the tree or derermine that there is no such decomposition. ## Input The first line contains a single integer $n$ ($2 \leq n \leq 10^{5}$) the number of nodes in the tree. Each of the next $n - 1$ lines contains two integers $a_i$ and $b_i$ ($1 \leq a_i, b_i \leq n$, $a_i \neq b_i$) — the edges of the tree. It is guaranteed that the given edges form a tree. ## Output If there are no decompositions, print the only line containing "_No_". Otherwise in the first line print "_Yes_", and in the second line print the number of paths in the decomposition $m$. Each of the next $m$ lines should contain two integers $u_i$, $v_i$ ($1 \leq u_i, v_i \leq n$, $u_i \neq v_i$) denoting that one of the paths in the decomposition is the simple path between nodes $u_i$ and $v_i$. Each pair of paths in the decomposition should have at least one common vertex, and each edge of the tree should be presented in exactly one path. You can print the paths and the ends of each path in arbitrary order. If there are multiple decompositions, print any. [samples] ## Note The tree from the first example is shown on the picture below: ![image](https://espresso.codeforces.com/3f106d1c8db145c1527aaf281f590b2685834455.png) The number next to each edge corresponds to the path number in the decomposition. It is easy to see that this decomposition suits the required conditions. The tree from the second example is shown on the picture below: ![image](https://espresso.codeforces.com/f6e87ca8aa608d6c85b1c9431aeda072fec49a96.png) We can show that there are no valid decompositions of this tree. The tree from the third example is shown on the picture below: ![image](https://espresso.codeforces.com/2b185153412f1373bcb378c1e203779f13959832.png) The number next to each edge corresponds to the path number in the decomposition. It is easy to see that this decomposition suits the required conditions.

Ramesses 对涉及树（无环无向连通图）的问题非常熟悉！他发明了一种新的有用树分解方法，但他不知道如何构造它，因此向你求助！这种分解要求将树的边划分为若干条简单路径，使得任意两条路径至少有一个公共顶点，且每条边恰好属于一条路径。请帮助 Ramesses 找到这样的树分解，或判定不存在这样的分解。第一行包含一个整数 $n$ ($2 lt.eq n lt.eq 10^5$)，表示树的节点数。接下来的 $n - 1$ 行每行包含两个整数 $a_i$ 和 $b_i$ ($1 lt.eq a_i, b_i lt.eq n$, $a_i eq.not b_i$) —— 表示树的边。保证给出的边构成一棵树。如果不存在分解，请仅输出一行 "_No_"。否则，第一行输出 "_Yes_"，第二行输出分解中路径的数量 $m$。接下来的 $m$ 行每行包含两个整数 $u_i$, $v_i$ ($1 lt.eq u_i, v_i lt.eq n$, $u_i eq.not v_i$)，表示分解中的一条路径是节点 $u_i$ 和 $v_i$ 之间的简单路径。分解中的每对路径必须至少有一个公共顶点，且树的每条边必须恰好出现在一条路径中。你可以任意顺序输出路径及每条路径的端点。如果存在多种分解，输出任意一种即可。第一个示例中的树如下图所示：每条边旁边的数字对应分解中的路径编号。容易看出此分解满足要求条件。第二个示例中的树如下图所示：我们可以证明该树不存在合法分解。第三个示例中的树如下图所示：每条边旁边的数字对应分解中的路径编号。容易看出此分解满足要求条件。 ## Input 第一行包含一个整数 $n$ ($2 lt.eq n lt.eq 10^5$)，表示树的节点数。接下来的 $n - 1$ 行每行包含两个整数 $a_i$ 和 $b_i$ ($1 lt.eq a_i, b_i lt.eq n$, $a_i eq.not b_i$) —— 表示树的边。保证给出的边构成一棵树。 ## Output 如果不存在分解，请仅输出一行 "_No_"。否则，第一行输出 "_Yes_"，第二行输出分解中路径的数量 $m$。接下来的 $m$ 行每行包含两个整数 $u_i$, $v_i$ ($1 lt.eq u_i, v_i lt.eq n$, $u_i eq.not v_i$)，表示分解中的一条路径是节点 $u_i$ 和 $v_i$ 之间的简单路径。分解中的每对路径必须至少有一个公共顶点，且树的每条边必须恰好出现在一条路径中。你可以任意顺序输出路径及每条路径的端点。如果存在多种分解，输出任意一种即可。 [samples] ## Note 第一个示例中的树如下图所示：每条边旁边的数字对应分解中的路径编号。容易看出此分解满足要求条件。第二个示例中的树如下图所示：我们可以证明该树不存在合法分解。第三个示例中的树如下图所示：每条边旁边的数字对应分解中的路径编号。容易看出此分解满足要求条件。

**Definitions** Let $ T = (V, E) $ be a tree with $ |V| = n $, $ |E| = n - 1 $. A *path decomposition* of $ T $ is a set $ \mathcal{P} = \{P_1, P_2, \dots, P_m\} $, where each $ P_i $ is a simple path in $ T $, such that: - $ \bigcup_{i=1}^m E(P_i) = E $, - $ E(P_i) \cap E(P_j) = \emptyset $ for all $ i \ne j $, - $ \forall i, j \in \{1, \dots, m\} $, $ V(P_i) \cap V(P_j) \ne \emptyset $. **Constraints** - $ 2 \le n \le 10^5 $, - $ T $ is a tree (connected, acyclic, undirected). **Objective** Determine whether there exists a path decomposition $ \mathcal{P} $ of $ T $ satisfying the above conditions. If yes, output any such decomposition; if no, output "No".

Samples

Input #1

Output #1

Yes
1
1 4

Input #2

Output #2

No

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "C. Useful Decomposition",
    "description": {
      "content": "Ramesses knows a lot about problems involving trees (undirected connected graphs without cycles)! He created a new useful tree decomposition, but he does not know how to construct it, so he asked you",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF981C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Ramesses knows a lot about problems involving trees (undirected connected graphs without cycles)!\n\nHe created a new useful tree decomposition, but he does not know how to construct it, so he asked you...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Ramesses 对涉及树（无环无向连通图）的问题非常熟悉！\n\n他发明了一种新的有用树分解方法，但他不知道如何构造它，因此向你求助！\n\n这种分解要求将树的边划分为若干条简单路径，使得任意两条路径至少有一个公共顶点，且每条边恰好属于一条路径。\n\n请帮助 Ramesses 找到这样的树分解，或判定不存在这样的分解。\n\n第一行包含一个整数 $n$ ($2 lt.eq n lt.eq 10^5$)，表示树...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T = (V, E) $ be a tree with $ |V| = n $, $ |E| = n - 1 $.  \nA *path decomposition* of $ T $ is a set $ \\mathcal{P} = \\{P_1, P_2, \\dots, P_m\\} $, where each $ P_i $ is a simple ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments