## A Counting Problem

View as PDF

Points: 15
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Given a bidirectional tree containing $$N$$ nodes, output the number of paths of odd length, and number of paths of even length. A path is of odd length if it contains an odd number of edges, and even length if it contains a positive even number of edges. A path is different from another path if the starting or ending nodes differ. For example, a path from $$a$$ to $$b$$ is different from a path from $$b$$ to $$a$$.

#### Input Specification

The first line will contain the integer $$N\ (1 \le N \le 10^5)$$, the number of nodes.

The next $$N-1$$ lines will each contain $$2$$ integers, $$a, b\ (1 \le a, b \le N)$$, indicating node $$a$$ and node $$b$$ are connected by an edge. It is guaranteed the entire tree is connected.

#### Output Specification

On the first line, output the number of even length paths.

On the second line, output the number of odd length paths.

#### Sample Input

5
1 3
2 3
4 3
4 5

#### Sample Output

8
12