FoxConnection2
SRM 604 · 2013-12-22 · by cgy4ever
SRM 604 · 2013-12-22 · by cgy4ever · Dynamic Programming
Problem Statement
Problem Statement
There are N cities in Treeland.
The cities are numbered 1 through N.
The roads in Treeland have the topology of a tree.
That is, there are exactly N-1 bidirectional roads in Treeland, each connecting a pair of cities, and it is possible to travel between any two cities along the roads.
You are given twoint[] s A and B that describe the tree.
Each of these int[] s has N-1 elements.
For each valid i, there is a road that connects the cities A[i] and B[i].
Currently, k foxes live in a forest in Treeland. They would like to move into cities. Each fox must live in a different city. Therefore, they must select exactly k different cities where they will live. Additionally, they have an important constraint: The set of cities inhabited by the foxes must be connected. That is, for any two different cities i and j that both contain a fox, all the cities on the (only) path between i and j must also contain a fox.
Let X be the number of ways in which we can choose k cities in Treeland in such a way that the constraint is satisfied. Return the value (X modulo 1,000,000,007). Two selections are different if and only if there is a city selected in one of them but not in the other. (Note that we are only selecting a set of cities, we are not assigning individual foxes to the cities.)
You are given two
Currently, k foxes live in a forest in Treeland. They would like to move into cities. Each fox must live in a different city. Therefore, they must select exactly k different cities where they will live. Additionally, they have an important constraint: The set of cities inhabited by the foxes must be connected. That is, for any two different cities i and j that both contain a fox, all the cities on the (only) path between i and j must also contain a fox.
Let X be the number of ways in which we can choose k cities in Treeland in such a way that the constraint is satisfied. Return the value (X modulo 1,000,000,007). Two selections are different if and only if there is a city selected in one of them but not in the other. (Note that we are only selecting a set of cities, we are not assigning individual foxes to the cities.)
Constraints
- N will be between 2 and 50, inclusive.
- A will contain exactly N-1 elements.
- Each element of A will be between 1 and N, inclusive.
- B will contain exactly N-1 elements.
- Each element of B will be between 1 and N, inclusive.
- The graph described by A and B will be a tree.
- k will be between 1 and N, inclusive.
Examples
0)
{1,2,3}
{2,3,4}
2
Returns: 3
Treeland looks as follows: 1-2-3-4. There are 3 ways to put 2 foxes: {1,2}, {2,3} or {3,4}.
1)
{1,1,1,1}
{2,3,4,5}
3
Returns: 6
There are 6 ways: {1,2,3}, {1,2,4}, {1,2,5}, {1,3,4}, {1,3,5} and {1,4,5}.
2)
{1,2,3,4}
{2,3,4,5}
3
Returns: 3
3)
{1,2,2,4,4}
{2,3,4,5,6}
3
Returns: 6
4)
{1,2,2,4,4}
{2,3,4,5,6}
5
Returns: 4
Submissions are judged against all 97 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class FoxConnection2 with a public method int ways(vector<int> A, vector<int> B, int k) · 97 test cases · 2 s / 256 MB per case