TheTreeAndMan
2015 TCO 1B · 2015-04-08 · by gridnevvvit
Problem Statement
You have a rooted tree with N vertices. All edges of the tree are directed away from the root. Hence, all vertices are reachable from the root.
The vertices are numbered 0 through N-1, with 0 being the root.
For each edge, the parent has a smaller number than the child.
You are given the description of the tree in a
A sequence M of 7 different vertices is called a Man if:
- The 2nd element of M is reachable from the 1st element of M
- The 3rd element of M is reachable from the 2nd element of M
- The 4th element of M is reachable from the 2nd element of M
- The 5th element of M is reachable from the 2nd element of M
- The 6th element of M is reachable from the 5th element of M
- The 7th element of M is reachable from the 5th element of M
- The six paths that correspond to the previous six items are disjoint. (I.e., they have no edges in common.)
Two Men are different if there is a vertex v that is among the seven vertices in one of them but not in the other. Note that the order of vertices does not matter. For example, if (1,2,3,4,5,6,7) is a valid Man, (1,2,3,4,5,7,6) is also valid and it is the same Man.
Let X be the number of different Men in the given tree. Compute and return the value (X modulo 1,000,000,007).
Constraints
- N will be between 2 and 2000, inclusive.
- parent will contain exactly N - 1 elements.
- For each valid i, parent[i] will be between 0 and i, inclusive.
{0,1,1,1,4,4}
Returns: 1
This is the Man:
{0,0,2,2,2,4,0,4,7,2,10,11,9,0,1,0}
Returns: 7
{0,0,2,2,3,1,0,1,5}
Returns: 0
{0,0,0,2,3,5,2,5,3,7,7,7,2}
Returns: 3
{0,0,1,2,2,2,1,4,2,9,0,1,5}
Returns: 0
Submissions are judged against all 90 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TheTreeAndMan with a public method int solve(vector<int> parent) · 90 test cases · 2 s / 256 MB per case