Text and implementation of this problem are kindly provided by Clive Fraser
aka CSFPython for which we are very grateful!
You are given a tree with N nodes, numbered 0 to N-1. The root node of the tree is node 0. You have to
find the value of the tree. This is the same as the value of the root node of the tree. (See explanation below)
The tree value can be quite large, so you are asked to give the result modulo 1000000007 (10^9 + 7).
Remember that the depth of a node is its distance from the root. So the root node has depth 0, all child nodes
of the root node have depth 1; children of these child nodes have depth 2 and so on. Remember also that a
leaf node is any node that has no children. The node to which any node is attached, joining it to the tree,
is called its parent node.
The value of any leaf node is equal to its depth. For other nodes we need to do a calculation to find the node
value. First we find the values of each of their child nodes. We take the biggest of these (p) and the
smallest (q). The value of the node is then p^3 * q^2. For example, if a node has three children with
values 5, 2 and 7 then p = 7 and q = 2, giving a node value of 7^3 * 2^2 = 1372. For a node with
only one child having a value of 3, we have p = 3 and q = 3, giving a node value of 3^3 * 3^2 = 243.
To check that you have understood the problem correctly, the following table gives all of the node values for
the tree of 21 nodes (numbered 0 to 20) in the example below (also it is represented in the picture above).
0 189076013219253356713152 = 273443105 modulo 1000000007
1 57395628
2 2
3 1
4 1
5 32
6 2
7 243
8 32
9 3
10 3
11 3
12 32
13 2
14 2
15 2
16 2
17 2
18 3
19 2
20 2
Note that the example has been made deliberately small to assist in explaining the problem.
The actual problem will describe a tree which is about 50 times bigger.
Input/Output description:
The first line of the input data will contain 2 space-separated integers N and M.
N is the number of nodes in the tree. These are numbered 0 to N-1.
M lines of data follow. Each of these lines contains 20 space-separated integers. These are the parent
nodes of nodes 1, 2, 3, etc. The first line contains the parents of nodes 1 to 20, the second line contains the parents of nodes 21 to 40, and so on until the parents of all nodes in the tree have been read.
Your answer is a single integer, the value of the root node (modulo 1000000007).
Example:
input:
21 1
0 1 0 0 0 1 1 0 7 7 7 0 8 12 5 1 12 7 1 12
answer:
273443105
This same tree is depicted in the image above, with "green" nodes marking leaves (without children). Values
are in form node_number : node_value, with root node value shown without modulo but in contracted form.