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 109+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 (k2).
  3. Every leaf is equidistant to the root node.

Input Specification

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

The next N1 lines will each contain two integers, ui and vi (1ui,viN), indicating that nodes ui and vi are connected by an edge.

Output Specification

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

Subtasks

Subtask 1 [27%]

N100

Subtask 2 [73%]

No additional constraints.

Sample Input for Subtask 1

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

Sample Output for Subtask 1

Copy
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

Copy
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

Copy
130

Comments

There are no comments at the moment.