DismantleTheTree | Topcoder Archive

Problem Statement

We have a weighted tree with N nodes, numbered 1 through N. You are given the description of the tree: the int[]s X, Y and edgeWeight, each with N-1 elements. For each i between 0 and N-2, inclusive, there is an edge that connects the nodes X[i] and Y[i], and the weight of this edge is edgeWeight[i].

You want to erase all edges of the tree as cheaply as possible. In each step, you can select any simple path that consists of edges of the same weight W, pay W, and erase all the edges that form the path.

(Note that you only pay W once, regardless of the length of the path. Also note that the entire path must still exist in the tree.)

Compute and return the minimum total cost you need to pay to erase all edges of the given tree.

Definition

Class:: DismantleTheTree
Method:: dismantle
Parameters:: int, int[], int[], int[]
Returns:: int
Method signature:: int dismantle(int N, int[] X, int[] Y, int[] weight)
(be sure your method is public)

Constraints

N will be between 2 and 1000, inclusive.
X, Y, and edgeWeight will each contain exactly N-1 elements.
All elements of X and Y will be between 1 and N, inclusive.
All elements of edgeWeight will be between 1 and 100, inclusive.
It is guaranteed that the input will be a tree.

Examples

```
4
```
```
{1, 2, 2}
```
```
{2, 3, 4}
```
```
{1, 2, 1}
```
```
Returns: 3
```
The tree looks as follows: 1 | |[1] | 3-------2-------4 [2] [1] In the optimal solution we pay 1 to remove the path 1-2-4 and then we pay 2 to remove the edge 2-3.
```
5
```
```
{1 ,1 ,5 ,3 }
```
```
{2 ,3 ,4 ,5 }
```
```
{2 ,2 ,2 ,1 }
```
```
Returns: 5
```
The tree looks as follows: [2] [2] [1] [2] 2-------1-------3-------5-------4 Note that we cannot erase all the edges with weight 2 at the same time, as they don't form a single simple path.

{1, 2, 3, 4, 4}

{3, 3, 4, 5, 6}

{10, 10, 10, 10, 10}

Returns: 30

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.