Leaf Count
EasyPractice library · +10 XPtreesarrays
You are given a tree represented by a parent array. The parent array P of size N describes a tree with N nodes, labeled from 0 to N-1. For each node i (from 1 to N-1), P[i] is the parent of node i. Node 0 is the root and has no parent (represented by P[0] = -1). A leaf node is a node with no children. Count and print the total number of leaf nodes in the tree.
Input
The first line contains an integer N (2 <= N <= 1000). The second line contains N integers P_0, P_1, ..., P_{N-1} (-1 <= P_i < N, P_0 = -1).
Output
Print a single integer: the number of leaf nodes.
Constraints
2 <= N <= 1000 -1 <= P_i < N P_0 = -1
Time limit 1 s (native code; slower languages get more)Memory 256 MB12 hidden tests
Example 1
Input
5 -1 0 0 1 1
Output
3
Tree: 0 is root. 1 and 2 are children of 0. 3 and 4 are children of 1. Leaves are 2, 3, 4.
Example 2
Input
3 -1 0 1
Output
1
Tree: 0 -> 1 -> 2. Leaf is 2.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
5 -1 0 0 1 1
Example 2 input
3 -1 0 1