FoxConnection2 | Topcoder Archive

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 two int[]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.)

Definition

Class:: FoxConnection2
Method:: ways
Parameters:: int[], int[], int
Returns:: int
Method signature:: int ways(int[] A, int[] B, int k)
(be sure your method is public)

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

```
{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}
```
```
{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}.
```
{1,2,3,4}
```
```
{2,3,4,5}
```
```
3
```
```
Returns: 3
```
```
{1,2,2,4,4}
```
```
{2,3,4,5,6}
```
```
3
```
```
Returns: 6
```
```
{1,2,2,4,4}
```
```
{2,3,4,5,6}
```
```
5
```
```
Returns: 4
```

{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

{2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}

Returns: 923263934

```
{2}
```
```
{1}
```
```
1
```
```
Returns: 2
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.