Connection Status:
Competition Arena > RestrictedLeaves

RestrictedLeaves

SRM 780 · 2020-03-06 · by misof

SRM 780 · 2020-03-06 · by misof · Dynamic Programming, Graph Theory
Class Name: RestrictedLeaves
Return Type: int
Method Name: count
Arg Types: (vector<int>)
Problem Statement

Problem Statement

Given is a rooted tree on N >= 4 vertices. The vertices are labeled 0 through N-1 in such a way that the parent always has a smaller number than its child. (Hence, vertex 0 is the root.)

The tree is such that each vertex that is not a leaf has at least two children.

The leaves of this tree can be ordered by running a depth-first search from the root. During the depth-first search, each vertex will visit its children ordered from the smallest to the largest label.

We will now define a new undirected graph G. Informally, G is obtained by drawing the tree and then drawing a cycle through all leaves of the tree, in their DFS order. More formally, the new graph G has the same vertices as the tree, and two vertices are considered adjacent in G if:

  • They are a parent and its child in the tree.
  • They are two leaves who are adjacent in the DFS order of all leaves.
  • They are the first and the last leaf in the DFS order of all leaves.

You are given a description of the tree: the int[] parent with N elements. Element 0 of parent is -1 and should be ignored. For each i > 0, parent[i] is the parent of i in the tree. Count all independent sets (of all sizes) in the graph G described above. Return that count modulo 10^9 + 7.

Notes

  • An independent set is a subset of vertices such that no two vertices in the subset are connected by an edge.

Constraints

  • parent will contain between 4 and 1000 elements, inclusive.
  • parent[0] will be -1.
  • For each i > 0, parent[i] will be between 0 and i-1, inclusive.
  • The tree described by parent will have degrees as described by the problem statement.
Examples
0)
{-1, 0, 0, 0, 0}
Returns: 8

The tree is a star with 0 as the root and 1, 2, 3, 4 as the leaves. The DFS order of leaves is {1, 2, 3, 4}. Graph G contains the following edges: 0-1, 0-2, 0-3, 0-4, 1-2, 2-3, 3-4, 4-1. The eight independent sets of its vertices are the empty set, the five 1-element sets, and the sets {1,3} and {2,4}.

1)
{-1, 0, 0, 1, 2, 1, 2}
Returns: 21

The DFS order of leaves is {3,5,4,6}. In G there is one empty independent set, seven 1-element sets, eleven 2-element sets (all non-edges), and the sets {0,3,4} and {0,5,6}.

2)
{-1, 0, 0, 1, 2, 1, 2, 1, 4, 4}
Returns: 75
3)
{-1, 0, 0, 0}
Returns: 5
4)
{-1, 0, 1, 1, 0}
Returns: 9

Submissions are judged against all 68 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class RestrictedLeaves with a public method int count(vector<int> parent) · 68 test cases · 2 s / 256 MB per case

Submitting as anonymous