PIB '20 P4 - Ninjaclasher the Perfect Man

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 0.5s
Memory limit: 256M

Author:
Problem types

Ninjaclasher, MCPT's self-proclaimed President, has an obsession with all things perfect. One day, while he was working on a tree problem, he began wondering how many perfect trees existed in the problem. As such, he has hired you to find the number of perfect trees on a given tree.

More specifically, he wants to know the number of non-empty subset of nodes in the tree that form a perfect tree, modulo 10^9+7. A subset of nodes is a perfect tree if there is a root of that subset of nodes that satisfies these properties:

  1. The subset of nodes forms a connected tree.
  2. Every non-leaf node in the tree has the same amount of children k (k \ge 2).
  3. Every leaf is equidistant to the root node.

Input Specification

The first line will contain the integer N (1 \le N \le 2000), the number of nodes in the tree.

The next N-1 lines will each contain two integers, u_i and v_i (1 \le u_i, v_i \le N), indicating that nodes u_i and v_i are connected by an edge.

Output Specification

The number of subset of nodes of the tree that form a perfect tree, modulo 10^9+7.

Subtasks

Subtask 1 [27%]

N \le 100

Subtask 2 [73%]

No additional constraints.

Sample Input for Subtask 1

8
1 2
1 3
1 4
2 5
2 6
4 7
4 8

Sample Output for Subtask 1

21

Explanation for Sample for Subtask 1

The following tree is given:

The following are the 21 perfect trees, with the roots in red:

Sample Input for Subtask 2

15
1 2
1 3
1 4
1 5
1 6
2 7
2 8
2 9
2 10
6 11
6 12
6 13
6 14
11 15

Sample Output for Subtask 2

130

Comments

There are no comments at the moment.