Bruce's Brittle Bridges

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

It is a well known fact that Sam is an incredibly talented programmer. However, his teacher Bruce is beginning to have doubts.

To test his suspicions, Bruce drops Sam off in a faraway island of N connected islands, joined by N-1 bidirectional bridges. However, the bridges are brittle, so bridge i can only be traversed a maximum of t_i times. Moreover, the i^\text{th} of the N islands houses a treasure chest of value v_i.

Right before Bruce leaves to teach Sam's class without him, he tells Sam that he has one chance to tell him the maximum value of treasure chests he can obtain. If he fails to do so, Bruce will leave Sam stranded on the island forever. However, Sam is unable to solve this problem. He passes it on to Daniel, who passes it on to you to solve!

Give that Sam starts at island 1 and can end at any island, help Daniel find the right answer for Sam!


For all subtasks:

1 \le v_i, t_i \le 10^9

1 \le A_i, B_i \le N

Subtask 1 [20%]

1 \le N \le 8

Subtask 2 [30%]

1 \le N \le 2 \times 10^3

Subtask 3 [50%]

1 \le N \le 2 \times 10^5

Input Specification

The first line of input will contain the integer N, the number of islands.

The second line of input will contain N positive integers v_i.

The next N-1 lines will contain A_i, B_i, and t_i, representing a bidirectional edge between A_i and B_i that can be traversed a maximum of t_i times.

Output Specification

Output one integer representing the maximum amount of treasure Sam can gather. Please note that 64-bit integers may be required for full marks.

Sample Input 1

4 8 5
1 2 2
2 3 2

Sample Output 1


Explanation for Sample Output 1

Sam's optimal path is 1 \to 2 \to 3, gathering 4 + 8 + 5 = 17 units of treasure. Note that Sam is able to return to his starting position, but this is not required for this case.

Sample Input 2

8 10 4 9 1
1 2 1
1 3 2
2 4 1
2 5 1

Sample Output 2


Explanation for Sample Output 2

Sam's optimal path is 1 \to 3 \to 1 \to 2 \to 4, gathering 8 + 4 + 0 + 10 + 9 = 31 units of treasure. Note that since each treasure chest can only be retrieved once, returning to island 1 doesn't grant additional treasure.


  • 20
    DM__Oscar  commented on March 3, 2021, 12:13 a.m.

    Let's go stuck on USACO silver gang!