Connection Status:
Competition Arena > TreeDistance

TreeDistance

TCO14 Round 3B · 2014-03-26 · by rng_58

TCO14 Round 3B · 2014-03-26 · by rng_58 · Dynamic Programming, Graph Theory, Math
Class Name: TreeDistance
Return Type: int
Method Name: countTrees
Arg Types: (vector<int>, int)
Problem Statement

Problem Statement

Cat Snuke has a tree with N vertices. The vertices are labeled 0 through N-1.

Snuke is able to modify the tree by performing a special operation. The operation consists of two steps. In the first step, he selects and removes an arbitrary edge of the tree. This divides the tree into two connected components. In the second step, he adds an arbitrary edge that connects those two components back into one tree.

You are given a int[] p that describes a tree, and an int K. The int[] p contains N-1 elements. For each i, the vertex p[i] and the vertex (i+1) are connected by an edge. Note that the initial labeling of the tree is such that for each i, p[i] is less than (i+1).

Snuke currently has the tree described by p. He may now modify it by repeatedly performing the operation described above. The number of operations Snuke will perform will be between 0 and K, inclusive.

Two trees are considered different if there are vertices p and q such that one of the trees contains the edge p-q but the other one does not. Return the number of different trees Snuke can produce, modulo 1,000,000,007.

Constraints

  • p will contain between 1 and 49 elements, inclusive. (This means that N will be between 2 and 50, inclusive.)
  • For each valid i, p[i] will be between 0 and i, inclusive.
  • K will be between 0 and 50, inclusive.
Examples
0)
{0, 0}
1
Returns: 3

There are three different trees for N=3. The one described by this p contains the edges 0-1 and 0-2. Snuke can turn it into either of the other two trees in a single operation.

1)
{0, 1, 2, 2, 0}
1
Returns: 28

Some of the trees for N=6 cannot be obtained from the given one in a single operation.

2)
{0, 1, 2, 2, 0}
2
Returns: 222

In two operations Snuke can produce some more trees, but not all of them. For example, Snuke would need three operations to produce the tree with the edges 0-1, 0-2, 0-3, 0-4, and 0-5.

3)
{0, 1, 2, 2, 0}
50
Returns: 1296

In 50 operations Snuke can produce all trees.

4)
{0, 1, 2, 2, 0}
0
Returns: 1

As no modifications are allowed, there is only one tree Snuke can produce in this test case.

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

Coding Area

Language: C++17 · define a public class TreeDistance with a public method int countTrees(vector<int> p, int K) · 136 test cases · 2 s / 256 MB per case

Submitting as anonymous