B. Christmas Spruce

Codeforces

IDCF913B

Time1000ms

Memory256MB

Difficulty—

implementationtrees

English · Original

Chinese · Translation

Formal · Original

Consider a rooted tree. A rooted tree has one special vertex called the root. All edges are directed from the root. Vertex _u_ is called a _child_ of vertex _v_ and vertex _v_ is called a _parent_ of vertex _u_ if there exists a directed edge from _v_ to _u_. A vertex is called a _leaf_ if it doesn't have children and has a parent. Let's call a rooted tree a _spruce_ if its every non-leaf vertex has at least 3 leaf children. You are given a rooted tree, check whether it's a spruce. The definition of a rooted tree can be found [here](https://goo.gl/1dqvzz). ## Input The first line contains one integer _n_ — the number of vertices in the tree (3 ≤ _n_ ≤ 1 000). Each of the next _n_ - 1 lines contains one integer _p__i_ (1 ≤ _i_ ≤ _n_ - 1) — the index of the parent of the _i_ + 1\-th vertex (1 ≤ _p__i_ ≤ _i_). Vertex 1 is the root. It's guaranteed that the root has at least 2 children. ## Output Print "_Yes_" if the tree is a spruce and "_No_" otherwise. [samples] ## Note The first example: ![image](https://espresso.codeforces.com/a028cc3eb93ff24e14e12c093bc7fd0e0d9f7a1a.png) The second example: ![image](https://espresso.codeforces.com/e6c7b518972d13e2572004d8ce21cda77de4c938.png) It is not a spruce, because the non-leaf vertex 1 has only 2 leaf children. The third example: ![image](https://espresso.codeforces.com/9af8f35bd8ce5823176fec24fc464c670bf95c3e.png)

考虑一棵有根树。有根树有一个特殊的顶点称为根。所有边都从根指向外。如果存在一条从顶点 #cf_span[v] 指向顶点 #cf_span[u] 的有向边，则称顶点 #cf_span[u] 是顶点 #cf_span[v] 的 _子节点_，顶点 #cf_span[v] 是顶点 #cf_span[u] 的 _父节点_。如果一个顶点没有子节点但有父节点，则称其为 _叶子_。我们称一棵有根树为 _松树_，如果它的每一个非叶子顶点都至少有 #cf_span[3] 个叶子子节点。给你一棵有根树，请判断它是否为松树。有根树的定义可在此处找到。第一行包含一个整数 #cf_span[n] —— 树中顶点的数量（#cf_span[3 ≤ n ≤ 1 000]）。接下来的 #cf_span[n - 1] 行每行包含一个整数 #cf_span[pi]（#cf_span[1 ≤ i ≤ n - 1]）—— 第 #cf_span[i + 1] 个顶点的父节点的编号（#cf_span[1 ≤ pi ≤ i]）。顶点 #cf_span[1] 是根。保证根至少有 #cf_span[2] 个子节点。如果树是松树，输出 "_Yes_"；否则输出 "_No_"。第一个例子：第二个例子：它不是松树，因为非叶子顶点 #cf_span[1] 只有 #cf_span[2] 个叶子子节点。第三个例子： ## Input 第一行包含一个整数 #cf_span[n] —— 树中顶点的数量（#cf_span[3 ≤ n ≤ 1 000]）。接下来的 #cf_span[n - 1] 行每行包含一个整数 #cf_span[pi]（#cf_span[1 ≤ i ≤ n - 1]）—— 第 #cf_span[i + 1] 个顶点的父节点的编号（#cf_span[1 ≤ pi ≤ i]）。顶点 #cf_span[1] 是根。保证根至少有 #cf_span[2] 个子节点。 ## Output 如果树是松树，输出 "_Yes_"；否则输出 "_No_"。 [samples] ## Note 第一个例子：第二个例子：它不是松树，因为非叶子顶点 #cf_span[1] 只有 #cf_span[2] 个叶子子节点。第三个例子：

Let $ T = (V, E) $ be a rooted tree with $ n $ vertices, where vertex $ 1 $ is the root. Let $ \text{parent}(v) $ denote the parent of vertex $ v \neq 1 $, and $ \text{children}(v) $ denote the set of children of vertex $ v $. A vertex $ v $ is a **leaf** if $ |\text{children}(v)| = 0 $ and $ v \neq 1 $. A vertex $ v $ is **non-leaf** if $ |\text{children}(v)| > 0 $. The tree $ T $ is a **spruce** if every non-leaf vertex has at least 3 leaf children. That is, for all $ v \in V $ such that $ |\text{children}(v)| > 0 $: $$ \left| \left\{ u \in \text{children}(v) \mid |\text{children}(u)| = 0 \right\} \right| \geq 3 $$ **Input:** - Integer $ n $, $ 3 \leq n \leq 1000 $ - For $ i = 1 $ to $ n-1 $: integer $ p_i $, the parent of vertex $ i+1 $, with $ 1 \leq p_i \leq i $ **Output:** "Yes" if $ T $ is a spruce; "No" otherwise.

Samples

Input #1

Output #1

Yes

Input #2

Output #2

No

Input #3

Output #3

Yes

API Response (JSON)

{
  "problem": {
    "name": "B. Christmas Spruce",
    "description": {
      "content": "Consider a rooted tree. A rooted tree has one special vertex called the root. All edges are directed from the root. Vertex _u_ is called a _child_ of vertex _v_ and vertex _v_ is called a _parent_ of ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF913B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Consider a rooted tree. A rooted tree has one special vertex called the root. All edges are directed from the root. Vertex _u_ is called a _child_ of vertex _v_ and vertex _v_ is called a _parent_ of ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "考虑一棵有根树。有根树有一个特殊的顶点称为根。所有边都从根指向外。如果存在一条从顶点 #cf_span[v] 指向顶点 #cf_span[u] 的有向边，则称顶点 #cf_span[u] 是顶点 #cf_span[v] 的 _子节点_，顶点 #cf_span[v] 是顶点 #cf_span[u] 的 _父节点_。如果一个顶点没有子节点但有父节点，则称其为 _叶子_。\n\n我们称一棵有根树为 _松树_...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ T = (V, E) $ be a rooted tree with $ n $ vertices, where vertex $ 1 $ is the root.  \nLet $ \\text{parent}(v) $ denote the parent of vertex $ v \\neq 1 $, and $ \\text{children}(v) $ denote the set ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments