Count the Leaves

Difficulty: 1100 4000 ms 128 MB

trees

The tree is rooted at node 1. A leaf is a non-root node with no children. Count the leaves (a single-node tree has 1).

Input: the first line has N; each of the next N−1 lines has an edge u v.

Output: the number of leaves.

Constraints:

• 1 ≤ N ≤ 10⁵

Sample Tests

5
1 2
1 3
3 4
3 5

3

2
1 2

1

Read the Editorial