Connection Status:
Competition Arena > DoubleTree

DoubleTree

SRM 633 · 2014-08-25 · by cgy4ever

SRM 633 · 2014-08-25 · by cgy4ever · Graph Theory
Class Name: DoubleTree
Return Type: int
Method Name: maximalScore
Arg Types: (vector<int>, vector<int>, vector<int>, vector<int>, vector<int>)
Problem Statement

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.

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,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.

1)
{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.

2)
{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.

3)
{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.

4)
{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.

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

Coding Area

Language: C++17 · define a public class DoubleTree with a public method int maximalScore(vector<int> a, vector<int> b, vector<int> c, vector<int> d, vector<int> score) · 144 test cases · 2 s / 256 MB per case

Submitting as anonymous