[Question]
  [
Let a counting tree be a rooted tree in which every node is labeled with the number of descendants it has.
We can represent such trees as ragged lists with each node being represented by a list containing its label followed by its children. For example the following is a counting tree:
```
[5,[2,[0],[0]],[0],[0]]
```
However the brackets themselves are redundant since the labels fully capture the structure of the counting tree. So we can represent them simply as lists of integers. The example above is:
```
[5,2,0,0,0,0]
```
However not all lists of integers represent a counting tree. For example:
```
[5,1,2,0,0,0]
```
This can't work because `2` must be a child of `1`, but it needs more descendants.
## Challenge
Take as input a non-empty list of non-negative integers and determine if it represents a counting tree as described above. Output one of two distinct consistent values, one if the input is a valid counting tree the other if it is not.
This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") so the goal is to minimize the size of your source code as measured in bytes.
## Test cases
## Valid
```
[5,2,0,0,0,0]
[5,2,1,0,0,0]
[5,2,1,0,1,0]
[5,3,1,0,0,0]
[6,5,4,3,2,1,0]
[0]
```
## Invalid
```
[0,0,0,0,0,0]
[5,2,1,1,0,0]
[5,2,0,1,0,0]
[5,3,1,0,1,0]
[6,2,1,0,0,0]
[5,3,1,0,0,1]
[5,2,3,0,0,0]
```
  
[Answer]
# [Nekomata](https://github.com/AlephAlpha/Nekomata) + `-e`, 13 bytes
```
qCᵉLR↔<a*$h→L
```
[Attempt This Online!](https://ato.pxeger.com/run?1=m70iLzU7PzexJHFNtJJurpKOgpJuqlLsgqWlJWm6FpsLnR9u7fQJetQ2xSZRSyXjUdsknyXFScnFUPkFN9dGm-oY6RhAYCwXmGeIwTOE8oyR5Mx0THVMgCJGUFkw1jHAMMsQiWeAxDNGMtkMzVaYPYZQfcZQOYirAQ)
---
Here is the original answer in an old version of Nekomata:
## [Nekomata](https://github.com/AlephAlpha/Nekomata/tree/07c871a41fe7a47b78da21b9fe1f06b1e5ded2c1) + `-e`, 16 bytes
```
qCᵉLR↔$-ᵐP∀*$h→L
```
This is a new golfing language I'm working on. It's still in a very early stage of development.
I haven't made the first release, so the link above is to the latest commit.
This is a non-deterministic language inspired by [Curry](https://curry.pages.ps.informatik.uni-kiel.de/curry-lang.org/), [Brachylog](https://github.com/JCumin/Brachylog) and other language. Functions in Nekomata may have multiple possible results, and the interpreter will choose the result via backtracking.
## Explanation
A port of [@Neil's Charcoal answer](https://codegolf.stackexchange.com/a/258011/9288).
```
qCᵉLR↔$-ᵐP∀*$h→L
                    # Take [5,2,0,0,0,0] as an example
                    # The stack is initialized with an infinite cycle of the input
q                   # Non-deterministically choose a contiguous subsequence of the input
                    # Take [2,0,0] as an example
                    # The stack is now ..., [5,2,0,0,0,0], [2,0,0]
 C                  # Uncons; pop a list and push the tail and the head
                    # The stack is now ..., [5,2,0,0,0,0], [0,0], 2
  ᵉL                # Check if the length of the tail is equal to the head
                    # The stack is still ..., [5,2,0,0,0,0], [0,0], 2 since the check passes
    R               # Range from 1 to n
                    # The stack is now ..., [5,2,0,0,0,0], [0,0], [1,2]
     ↔              # Reverse
                    # The stack is now ..., [5,2,0,0,0,0], [0,0], [2,1]
      $             # Swap
                    # The stack is now ..., [5,2,0,0,0,0], [2,1], [0,0]
       -            # Subtract
                    # The stack is now ..., [5,2,0,0,0,0], [2,1]
        ᵐP          # Check if all elements of the list are positive
                    # The stack is still ..., [5,2,0,0,0,0], [2,1] since the check passes
          ∀         # Find all possible results of a non-deterministic computation
                    # The stack is now ..., [5,2,0,0,0,0], [[3,4,3,2,1],[2,1],[],[],[],[]]
           *        # Multiply; this will fail if the two lists has different lengths
                    # The stack is now ..., [[15,20,15,10,5],[4,2],[],[],[],[]]
            $       # Swap
                    # Note that there are infinite many copies of the input on the stack
                    # The stack is now ..., [[15,20,15,10,5],[4,2],[],[],[],[]], [5,2,0,0,0,0]
             h      # Head of a list
                    # The stack is now ..., [[15,20,15,10,5],[4,2],[],[],[],[]], 5
              →     # Increment
                    # The stack is now ..., [[15,20,15,10,5],[4,2],[],[],[],[]], 6
               L    # Check if the length of the list is equal to the number
                    # The check passes, so there is a result
```
The flag `-e` set the interpreter to `CheckExistence` mode, which prints `True` if the computation has any result, and `False` otherwise. We don't care what the result really is.
[Answer]
# [Vyxal](https://github.com/Vyxal/Vyxal), 17 bytes
```
ʀėṠ:Ẋ'ɖ↔ꜝnF;?ḣL≠∨
```
[Try it Online!](https://vyxal.pythonanywhere.com/#WyJBIiwiIiwiyoDEl+G5oDrhuoonyZbihpTqnJ1uRjs/4bijTOKJoOKIqCIsIiIsIls1LDIsMCwwLDAsMF1cbls1LDIsMSwwLDAsMF1cbls1LDIsMSwwLDEsMF1cbls1LDMsMSwwLDAsMF1cbls2LDUsNCwzLDIsMSwwXVxuWzBdXG5bMCwwLDAsMCwwLDBdXG5bNSwyLDEsMSwwLDBdXG5bNSwyLDAsMSwwLDBdXG5bNSwzLDEsMCwxLDBdXG5bNiwyLDEsMCwwLDBdXG5bNSwzLDEsMCwwLDFdXG5bNCwzLDEsMCwwLDBdIl0=)
Outputs a falsy value if it is a counting tree and a truthy if it's not.
Uses the fact that it is a counting tree iff
1. the first number is equal to the length of the rest of the list
2. for each pair of values `a`, `b` at indices `i`, `j` respectively the inclusive ranges `[i, i+a]` and `[j, j+b]` are either disjoint or one is a subset of the other
Get all inclusive ranges.
```
ʀ   # elementwise inclusive range from 0
 ė  # enumerate
  Ṡ # elementwise sum
```
Get all pairs and keep only those that don't satisfy 2.
```
:         # duplicate
 Ẋ        # cartesian product
  '     ; # filter by:
          #                        [[1,2,3],[3,4]]
   ɖ↔     #   scan by intersection [[1,2,3],[3]]
     ꜝ    #   keep truthy          [[1,2,3],[3]]
      n   #   push argument        [[1,2,3],[3]], [[1,2,3],[3,4]]
       F  #   set difference       [[3]]
          #   empty are falsy, non-emtpy are truthy
```
Check if 1. is not satisfied and combine the two.
```
?     # push input
 ḣ    # head extract
  L   # length
   ≠  # not equal
    ∨ # or
```
[Answer]
# [Curry (PAKCS)](https://www.informatik.uni-kiel.de/%7Epakcs/index.html), 36 bytes
```
f[0]=1
f(a:b++c)=f b*f(a-length b:c)
```
[Attempt This Online!](https://ato.pxeger.com/run?1=m706ubSoqDK-IDE7uXjBgqWlJWm6FjdV0qINYm0NudI0Eq2StLWTNW3TFJK0gDzdnNS89JIMhSSrZE2I2m25iZl5CrYKaQrRpjpGOgYQGAuRhBkIAA)
[Answer]
# [Python](https://www.python.org), 63 bytes
```
f=lambda T,*t:T!=len(t)or T>0<f(T-(x:=t[0]+1),*t[x:])|f(*t[:x])
```
[Attempt This Online!](https://ato.pxeger.com/run?1=m72soLIkIz9vwYKlpSVpuhY37dNscxJzk1ISFUJ0tEqsQhRtc1LzNEo084sUQuwMbNI0QnQ1KqxsS6INYrUNNYFKoiusYjVr0jSALKuKWE2oMappQA05Cpl5CvkFQP0GmlZcCgVFmXklGkCVqWWJORo5mppQxQtuLog21THSMYDAWC4wzxCDZwjlGSPJmemY6pgARYygsmCsY4BhliESzwCJZ4xkshmarTB7DGO5IA4FAA)
Returns False for trees and True for fakes.
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), ~~28~~ 23 bytes
```
∧⁼§θ⁰⊖Ｌθ⬤θ⬤✂θ⁺ικκ±¹¬›λμ
```
[Try it online!](https://tio.run/##HYrBCsIwEER/JccNrNAKnjwFFBGkFDyWHkKytKHblKSp@PcxcWAYHm/MrKPZNOfcR@cTKG/hHg7NO6j09Ja@EFA0EsWNTKSVfCILL/JTmiFIWYRirp86b3aGKvR87OBQLMUvKDqadCJo673bEjwiFY7AKFb5zzXnYbjgGVtsascxnz78Aw "Charcoal – Try It Online") Link is to verbose version of code. Outputs a Charcoal boolean, i.e. `-` for a counting tree, nothing if not. Explanation: Based on @AndrovT's approach, the first element must be one less than the length, then given any element `e`, the next `e` elements must all be less than the sequence from `e` down to `1`, although the code actually extracts the elements in reverse so that within their slice they must not exceed their 0-based index.
```
   θ                    Input array
  § ⁰                   First element
 ⁼                      Equals
       θ                Input array
      Ｌ                 Length
     ⊖                  Decremented
∧                       Logical And
         θ              Input array
        ⬤               All elements satisfy
            θ           Input array
           ✂            Sliced from
              ι         Current value
             ⁺          Plus
               κ        Current index
                κ       To current index
                 ±¹     In reverse
          ⬤             All elements satisfy
                     λ  Inner value
                   ¬›   Is not greater than
                      μ Inner index
                        Implicitly print
```
Example: For the input `[5,2,1,0,1,0]`, the length is `6` so the first element must be `5`, then the subsequent `5` elements must be less than `5,4,3,2,1`; the `2` elements after the `2` must be less than `2,1` and the `1` element after each `1` must be less than `1`. (Trivially the `0` elements after each `0` satisfy the property as well.)
Previous 28-byte approach:
```
Ｆθ«⊞υιＷ∧υ¬↨υ⁰≧⁻¬⊟υυ¬υ»¿∨υ⊖ⅈ⎚
```
[Try it online!](https://tio.run/##JYw9C8IwFEXn5ldkfIEIVXDqVO1aLU5C6RDatHkQk5oPHcTfHhu8cOFyuJxRCTdaoVOaraPwZPRDii56BZFTZBUp3gq1pFCbKaOLDXASXuZdsi20FWvtPS7mhosK0KKJ/v/r7AqRMU5j9nQOTYDMN1aRL8GZwtVlUSNHJx/SBDnBHbL0rKVwwKqU@v7ID3zPy9xhSLuX/gE "Charcoal – Try It Online") Link is to verbose version of code. Outputs a Charcoal boolean, i.e. `-` for a counting tree, nothing if not. Explanation:
```
Ｆθ«
```
Loop over the input integers.
```
⊞υι
```
Push them to the predefined empty list.
```
Ｗ∧υ¬↨υ⁰
```
While the list ends in `0`...
```
≧⁻¬⊟υυ
```
... remove the trailing `0` and decrement the remaining elements.
```
¬υ
```
Count the number of counting trees found.
```
»¿∨υ⊖ⅈ⎚
```
Check that there was exactly one counting tree and that it ended with the last element.
[Answer]
# [Retina 0.8.2](https://github.com/m-ender/retina/wiki/The-Language/a950ad7d925ec9316e3e2fb2cf5d49fd15d23e3d), 61 bytes
```
\d+
$*
+%`^((1)*)1(1*),(\1(?!1)(?<-2>,1*)*)(?(2)^)
$4¶$3
^¶*$
```
[Try it online!](https://tio.run/##K0otycxL/K@q4Z7wPyZFm0tFi0tbNSFOQ8NQU0vTUMNQS1NHI8ZQw17RUFPD3kbXyE4HKKQFZGsYacZpcqmYHNqmYswVd2iblsr//6Y6RjoGEMgFYhuisQ3BbGO4uJmOqY4JkA@W5QJCHQM0/YZwtgGcbQw3ywzFDpi5hgA "Retina 0.8.2 – Try It Online") Link includes test cases. Explanation: Port of @alephalpha's Curry answer.
```
\d+
$*
```
Convert to unary.
```
+%`^((1)*)1(1*),(\1(?!1)(?<-2>,1*)*)(?(2)^)
$4¶$3
```
Repeatedly split each rooted tree into its first branch and remaining branches.
```
^¶*$
```
Check that there are only twigs left.
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), 19 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
ŒʒćsgQ}εāR‹}˜P*ćsgQ
```
Inspired by [*@Neil*'s top Charcoal](https://codegolf.stackexchange.com/a/258011/52210), which is a port of [*@AndrovT*'s Vyxal answer](https://codegolf.stackexchange.com/a/258020/52210).
[Try it online](https://tio.run/##yy9OTMpM/f//6KRTk460F6cH1p7beqQx6FHDztrTcwK0wEL//0eb6RjpGOoYgGAsAA) or [verify all test cases](https://tio.run/##yy9OTMpM/V9Waa@k8KhtkoKSfaXL/6OTTk060l6cHlh7buuRxqBHDTtrT88J0AIL/df5Hx1tqmOkYwCBsTpgniEGzxDKM0aSM9Mx1TEBihhBZYFYIdpAxwDDMEMkngESzxjJaDM0a2EWGUL1GUPlYgE).
**Explanation:**
```
Œ           # Get all sublists of the (implicit) input-list
 ʒ          # Filter it by:
  ć         #  Extract head; pop and push remainder-list and first item seperately
   s        #  Swap so the remainder-list is at the top of the stack
    g       #  Pop and push its length
     Q      #  Check if the length of the remainder-list and first item are equal
 }ε         # After the filter: map over each remaining sublist:
   ā        #  Push a list in the range [1,length] (without popping the list)
    R       #  Reverse it to [length,1]
     ‹      #  Element-wise less-than check: [a<length,b<length-1,...,y<2,z<1]
  }˜        # After the map: flatten the list of checks
    P       # Product to check if all were truthy
     *      # Multiply this 1/0 to each value in the (implicit) input-list
      ćsgQ  # Do a similar check as before within the filter on the input-list itself
            # (after which the result is output implicitly)
```
I've been unable to find anything shorter for `*ćsgQ` which works for both the `[0,0,0,0,0,0]` and `[6,2,1,0,0,0]` test cases. Checking whether the input-list is in the filtered list of sublists is an equal-bytes alternative:
```
ŒéʒćsgQ}¤IÊªεāR‹}˜P
```
[Try it online](https://tio.run/##yy9OTMpM/f//6KTDK09NOtJenB5Ye2iJ5@GuQ6vObT3SGPSoYWft6TkB//9Hm@kY6RjqGIBgLAA) or [verify all test cases](https://tio.run/##yy9OTMpM/V9Waa@k8KhtkoKSfaXL/6OTDq88NelIe3F6YO2hJZWHuw6tOrf1SGPQo4adtafnBPzX@R8dbapjpGMAgbE6YJ4hBs8QyjNGkjPTMdUxAYoYQWWBWCHaQMcAwzBDJJ4BEs8YyWgzNGthFhlC9RlD5WIB).
**Additional explanation:**
```
 é          # Sort the sublists by length (shortest to longest)
  ¤         # Push the last sublist after the filter (without popping the list of lists)
   IÊ       # Check that it's NOT equals to the input-list
     ª      # Append this 0 or 1 to the list of sublists
            # (`āR‹` will succeed for 0 and fail for 1)
```
[Answer]
# [JavaScript (Node.js)](https://nodejs.org), 64 bytes
```
T=t=>t.shift()!=t.length|C(t)
C=$=>$>C&&C($.splice($[0]+1))|T($)
```
[Try it online!](https://tio.run/##hY@9CoMwFIV336IQJJemIdHqFpe8gps4iI0/JSTShE6@e1oo7VKN3PE7H@eee/fsXP@YF38x9qbCIEItvKg8ddM8eAwn4alWZvTTKrGHRAokKlTJNJUYUbfouVcYNaw9c4C1xghCb42zWlFtRzzgpiAZYZ9rAZINyg8p36F5xC1JQa7vRLZl/6UZYYdf8ghlEZpHNpQH@78L@U5v/nPDCw "JavaScript (Node.js) – Try It Online")
Code with comments:
```
isTree = tree =>
  tree[0] + 1 === tree.length &&
  isChildren(tree.slice(1))
isChildren = children =>
  children.length === 0 ||
    isTree(children.slice(0, children[0] + 1)) &&
    isChildren(children.slice(children[0] + 1))
```
Changing `!=` into `-` makes it 64 bytes by returning truthy vs. falsy.
~~-1~~-2 byte by l4m2.
[Answer]
# [Haskell](https://www.haskell.org), ~~85~~ 65 bytes
*-20 bytes thanks to [@Wheat Wizard](https://codegolf.stackexchange.com/users/56656/wheat-wizard)*
```
h(n:w)=f(n:take n w)&&h(drop n w)
h _=1>0
f(n:w)=h w&&n==length w
```
[Attempt This Online!](https://ato.pxeger.com/run?1=jZG_CsIwEMZxzVPcIKWFKI3VIkIEFzc3wUGkBE1NscbSRAruPoWLi_hM-jQG459SKkjgjvvxcffl7nQVTG14mp7Pl72OW_3bSLhyUHg0NkmzDQcJhec4wl3lu-xZIAERJUMfxVYpoHAcSWnK5Vqbwja6N46aKx0tmeIKKAKYw7yHO9i3b2EItoTUElIiQUUT4h7uGtopqT4Z-7UzSIX4FRJUpoY1zt4-SKlP8NUsEGJSFTx_fXia7zn-GcYsVX9F03bLEgkUtiybRJDlidTQhEOSzRKzcdel1IM2xB6UVv5yYq_xPu8D)
[Answer]
# [tinylisp 2](https://github.com/dloscutoff/tinylisp2), 88 bytes
```
(d F(\(L)(? L(*(<(h L)(# L))(F(](h L)(t L)))(F([(h L)(t L))))1
(\(L)(*(F L)(=(h L)(#(t L
```
The submission is the anonymous function in the second line.
You can try it at [Replit](https://replit.com/@dloscutoff/tinylisp2). Example session:
```
tl2> (d F(\(L)(? L(*(<(h L)(# L))(F(](h L)(t L)))(F([(h L)(t L))))1
F
tl2> (\(L)(*(F L)(=(h L)(#(t L
(() (L) (* (F L) (= (h L) (# (t L)))))
tl2> (d G _)
G
tl2> (G (list 5 2 1 0 1 0))
1
```
### Explanation
Our recursive helper function, `F`, analyzes a list as follows:
* Is it empty? Return `1` (truthy).
* Otherwise, split the list, conceptually, into head (first element) and tail (remaining elements).
	+ Is the head greater than or equal to the list's total length? (This means the root of this subtree doesn't have enough children.) Return `0` (falsey).
	+ Split the tail at the index given by the head. Recurse over each of these sublists. Return `1` if both results are `1`; otherwise return `0`.
```
(d F(\(L)(? L ... 1)))
(d F                 ) ; Define F as
    (\(L)           )  ; Lambda function taking list L
         (? L      )   ; If L is nonempty
              ...      ; (see below)
                  1    ; Else, return 1
(*(<(h L)(# L))(F(](h L)(t L)))(F([(h L)(t L))))
(*                                             ) ; Multiply these (logical AND):
  (<(h L)(# L))                                  ; 1. Head of L < length of L
               (F             )                  ; 2. Recursive call on:
                 (]          )                   ;    Take
                   (h L)                         ;    (head of L) elements
                        (t L)                    ;    from tail of L
                               (F             )  ; 3. Recursive call on:
                                 ([          )   ;    Drop
                                   (h L)         ;    (head of L) elements
                                        (t L)    ;    from tail of L
```
`F` verifies that a list represents a "forest" of zero or more counting trees concatenated. Our main function also needs to verify that we have exactly one counting tree. To do so, we first call `F` on the list, and then check whether the head is exactly equal to the length of the tail.
```
(\(L)(*(F L)(=(h L)(#(t L)))))
(\(L)                        ) ; Lambda function taking list L
     (*                     )  ; Multiply these (logical AND):
       (F L)                   ; 1. Call F on L
            (=             )   ; 2. These are equal:
              (h L)            ;    Head of L
                   (#(t L))    ;    Length of tail of L
```
[Answer]
# JavaScript (ES6), 75 bytes
Returns \$0\$ for valid, or \$1\$ for invalid.
```
f=([v,...a],s=v)=>v+1&&a.length!=s|f(a.slice(v=a[0]),s-++v)|f(a.slice(0,v))
```
[Try it online!](https://tio.run/##hZCxDoIwGIR338IF2vDTtCBsdfcFXGqHBgpimmIs6eS7V6PRYGIh/3bfXf7cXZRXrrkN1ym3Y6tD6DgSHgghSoLjHvO9z1iSKGK07afzlrt7hxRxZmg08lwJKjG4PMs8ngEKHuPQjNaNRhMz9igVR2WGVqZ4M5c7JCoogL5P4r@UrVIWoeVCtoYKdk9HEUm/tB8xPVlxsD7SgwJd7cEWKF2g5ULLemWhzwYs8rf8ZsMD "JavaScript (Node.js) – Try It Online")
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 147 bytes
```
(a=#;l=Length@a;And@@(IntervalMemberQ[#1,#2]||Length@IntervalIntersection[#1,#2]==0&@@@Subsets[Interval@{#,#+a[[#]]}&/@Range@l,{2}])&&a[[1]]==l-1)&
```
[Try it online!](https://tio.run/##PYvLCoMwFET3/Y1AUHpLE/vYSOB2WWihj2XIItpgBE1B0240325FtMxiYM6ZWntrau3LXA9WDJEWJK3ExbjCW9Tpyb0Qo7Pzpvnq6mrqzDR3STiQRPX9rC146tbkvny72RGCUUR8frLW@FYuJnYEyFpLSZQKdIsP7QqDFXRJUDGlI@Bq/FYbHtPh1pTOo8XuAAnwMQxYWP3XIxxgD7uJsTD8AA "Wolfram Language (Mathematica) – Try It Online")
I was looking at the problem in terms of interval arithmetic, and it seems got the same algorithm as @AndrovT. Unfortunately, Mathematica has almost no shorthands for cool functions, so code looks huge (
Explained:
```
(*Total logic And*)
And @@
 (*In True case intervals must be disjointed or nested*)
 (IntervalMemberQ[#1, #2] || 
     Length@IntervalIntersection[#1, #2] == 0 & @@@
   (*All subsets length 2*)
   Subsets[
    (*All intervals i + array[i]*)
    Interval@{#, # + a[[#]]} & /@ Range@l
    , {2}])
        (*Is first element equal length of the rest*)
        && a[[1]] == l - 1 &
```
]