E. Tree Constructing

Codeforces

IDCF1003E

Time4000ms

Memory256MB

Difficulty—

constructive algorithmsgraphs

English · Original

Chinese · Translation

Formal · Original

You are given three integers $n$, $d$ and $k$. Your task is to construct an undirected tree on $n$ vertices with diameter $d$ and degree of each vertex at most $k$, or say that it is impossible. An undirected tree is a connected undirected graph with $n - 1$ edges. Diameter of a tree is the maximum length of a simple path (a path in which each vertex appears at most once) between all pairs of vertices of this tree. Degree of a vertex is the number of edges incident to this vertex (i.e. for a vertex $u$ it is the number of edges $(u, v)$ that belong to the tree, where $v$ is any other vertex of a tree). ## Input The first line of the input contains three integers $n$, $d$ and $k$ ($1 \le n, d, k \le 4 \cdot 10^5$). ## Output If there is no tree satisfying the conditions above, print only one word "_NO_" (without quotes). Otherwise in the first line print "_YES_" (without quotes), and then print $n - 1$ lines describing edges of a tree satisfying the conditions above. Vertices of the tree must be numbered from $1$ to $n$. You can print edges and vertices connected by an edge in any order. If there are multiple answers, print any of them.1 [samples]

给定三个整数 $n$、$d$ 和 $k$。你的任务是构造一棵包含 $n$ 个顶点的无向树，使其直径为 $d$，且每个顶点的度数不超过 $k$；若不可能，则指出不可能。无向树是一个具有 $n - 1$ 条边的连通无向图。树的直径是该树中所有顶点对之间最简单路径（每个顶点至多出现一次的路径）的最大长度。顶点的度数是指与该顶点相连的边的数量（即对于顶点 $u$，它是属于树的边 $(u, v)$ 的数量，其中 $v$ 是树中的任意其他顶点）。输入的第一行包含三个整数 $n$、$d$ 和 $k$（$1 lt.eq n, d, k lt.eq 4 dot.op 10^5$）。如果不存在满足上述条件的树，请仅输出一个单词 "_NO_"（不含引号）。否则，第一行输出 "_YES_"（不含引号），然后输出 $n - 1$ 行，描述满足上述条件的树的边。树的顶点编号必须为 $1$ 到 $n$。你可以任意顺序输出边以及边连接的顶点。如果有多个答案，输出任意一个即可。1 ## Input 输入的第一行包含三个整数 $n$、$d$ 和 $k$（$1 lt.eq n, d, k lt.eq 4 dot.op 10^5$）。 ## Output 如果不存在满足上述条件的树，请仅输出一个单词 "_NO_"（不含引号）。否则，第一行输出 "_YES_"（不含引号），然后输出 $n - 1$ 行，描述满足上述条件的树的边。树的顶点编号必须为 $1$ 到 $n$。你可以任意顺序输出边以及边连接的顶点。如果有多个答案，输出任意一个即可。1 [samples]

**Definitions** Let $ n, d, k \in \mathbb{Z}^+ $ with $ 1 \leq n, d, k \leq 4 \cdot 10^5 $. Let $ T = (V, E) $ be an undirected tree with: - $ |V| = n $, - $ |E| = n - 1 $, - Diameter $ \mathrm{diam}(T) = d $, - $ \deg(v) \leq k $ for all $ v \in V $. **Constraints** 1. $ 1 \leq n \leq 4 \cdot 10^5 $ 2. $ 1 \leq d \leq 4 \cdot 10^5 $ 3. $ 1 \leq k \leq 4 \cdot 10^5 $ **Objective** Determine whether there exists a tree $ T $ satisfying: - $ \mathrm{diam}(T) = d $, - $ \max_{v \in V} \deg(v) \leq k $. If such a tree exists, output: - "YES", followed by $ n - 1 $ edges (as pairs of vertices). Otherwise, output: - "NO".

Samples

Input #1

6 3 3

Output #1

Input #2

6 2 3

Output #2

NO

Input #3

10 4 3

Output #3

Input #4

8 5 3

Output #4

API Response (JSON)

{
  "problem": {
    "name": "E. Tree Constructing",
    "description": {
      "content": "You are given three integers $n$, $d$ and $k$. Your task is to construct an undirected tree on $n$ vertices with diameter $d$ and degree of each vertex at most $k$, or say that it is impossible. An ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF1003E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given three integers $n$, $d$ and $k$.\n\nYour task is to construct an undirected tree on $n$ vertices with diameter $d$ and degree of each vertex at most $k$, or say that it is impossible.\n\nAn ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定三个整数 $n$、$d$ 和 $k$。\n\n你的任务是构造一棵包含 $n$ 个顶点的无向树，使其直径为 $d$，且每个顶点的度数不超过 $k$；若不可能，则指出不可能。\n\n无向树是一个具有 $n - 1$ 条边的连通无向图。\n\n树的直径是该树中所有顶点对之间最简单路径（每个顶点至多出现一次的路径）的最大长度。\n\n顶点的度数是指与该顶点相连的边的数量（即对于顶点 $u$，它是属于树的边 $(u, ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, d, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq n, d, k \\leq 4 \\cdot 10^5 $.  \n\nLet $ T = (V, E) $ be an undirected tree with:  \n- $ |V| = n $,  \n- $ |E| = n - 1 $,  \n- Diameter $ \\ma...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments