DoubleTree | Topcoder Archive

Problem Statement

You have two trees with the same number of nodes. The nodes in each tree are labeled 0 through n-1.

You are given four int[]s with n-1 elements each: a, b, c, and d. The int[]s a and b describe the first tree: for each valid i, the first tree contains an edge between nodes labeled a[i] and b[i]. The int[]s c and d describe the second tree in the same way.

Each of the values 0 through n-1 has an assigned integer score. These scores are given in an int[] score. Note that some of the scores may be negative.

Your goal is to select a subset S of the set {0, 1, ..., n-1} with the following properties:

In the first tree, the nodes with the labels in S induce a connected subgraph (a subtree of the original tree).
In the second tree, the nodes with the labels in S also induce a connected subgraph.

Return the largest possible sum of scores assigned to the elements of such a subset S.

Definition

Class:: DoubleTree
Method:: maximalScore
Parameters:: int[], int[], int[], int[], int[]
Returns:: int
Method signature:: int maximalScore(int[] a, int[] b, int[] c, int[] d, int[] score)
(be sure your method is public)

Notes

As there are only finitely many possible subsets S and the empty subset always has the desired properties, the return value is always correctly defined.

Constraints

n will be between 2 and 50, inclusive.
a and b will describe a tree with exactly n ndoes.
c and d will describe a tree with exactly n ndoes.
score will contain exactly n elements.
Each element in score will be between -1,000 and 1,000, inclusive.

Examples

```
{0,0,1}
```
```
{1,3,2}
```
```
{0,0,3}
```
```
{1,3,2}
```
```
{1000,24,100,-200}
```
```
Returns: 1024
```
The best subset we can choose is {0,1}. The nodes labeled 0 and 1 are connected by an edge in each of the trees. Note that we cannot choose {0,1,2} as in the second tree we cannot get from 0 to 2 without going through 3.
```
{0,0,1}
```
```
{1,3,2}
```
```
{0,0,3}
```
```
{1,3,2}
```
```
{1000,24,100,200}
```
```
Returns: 1324
```
As in this case all scores are positive, the best solution is to select all labels.
```
{0,0,1}
```
```
{1,3,2}
```
```
{0,0,3}
```
```
{1,3,2}
```
```
{-1000,-24,-100,-200}
```
```
Returns: 0
```
As in this case all scores are negative, the best solution is to select no labels at all.
```
{0,0,1}
```
```
{1,3,2}
```
```
{0,0,3}
```
```
{1,3,2}
```
```
{-1000,24,100,200}
```
```
Returns: 200
```
The optimal solution is to choose the subset {3} - a single node is connected.
```
{0,0,1,1,2,2}
```
```
{1,2,3,4,5,6}
```
```
{0,0,1,1,2,2}
```
```
{1,2,3,4,5,6}
```
```
{-3,2,2,-1,2,2,-1}
```
```
Returns: 5
```
In this test case the two trees are identical. The answer is the maximum score of a subtree of this tree.

{0,0,1,1,2,2}

{1,2,3,4,5,6}

{0,0,0,0,0,0}

{1,2,3,4,5,6}

{-3,2,2,-1,2,2,-1}

Returns: 5

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.