Several villages are connected by roads that form a tree. Every village has a weekend market with an expected earning.

Choose which markets will remain open. When a market is open, every directly connected village loses exactly customerLoss from its earnings.

Opening a market does not directly reduce its own earnings. However, an open market loses earnings for each neighboring market that is also open.

Only the final earnings of open markets are counted. Closed markets contribute nothing.

Return the maximum total earnings that can be obtained.

Class

VillageMarketPlanner

Method

maximumWeekendEarnings

long maximumWeekendEarnings( int villageCount, List<String> roads, List<Integer> marketEarnings, int customerLoss)

Parameters

• villageCount: The number of villages.
• roads: The roads between villages. Each string is formatted as "firstVillage,secondVillage".
• marketEarnings: The expected earning of every market. marketEarnings.get(i) belongs to village i.
• customerLoss: The earning lost because of one open neighboring market.

Returns

Return the maximum possible total final earnings of all open markets. Return 0 if leaving every market closed is optimal.

Market Rules

• Each market is either open or closed.
• If a market has openNeighborCount open neighbors, its final earning is: marketEarnings.get(i) - openNeighborCount * customerLoss .
• Two adjacent open markets reduce each other's earnings.
• Reductions caused by different open neighbors are added together.
• The final earning of an open market may be negative.
• Closed markets are not included in the returned total.
• It is allowed to leave all markets closed.

Input Representation

• Villages are numbered from 0 to villageCount - 1.
• A road string "u,v" represents a bidirectional road between villages u and v.
• The order of strings in roads does not affect the result.

Constraints

• 1 ≤ villageCount ≤ 200,000
• roads.size() = villageCount - 1
• marketEarnings.size() = villageCount
• -1,000,000,000 ≤ marketEarnings.get(i) ≤ 1,000,000,000
• 0 ≤ customerLoss ≤ 1,000,000,000
• 0 ≤ firstVillage, secondVillage < villageCount
• firstVillage != secondVillage
• Every string in roads contains exactly two comma-separated village identifiers.
• The roads form a connected tree.
• The returned value fits in a signed long.

Examples

Example 1

maximumWeekendEarnings( villageCount = 3, roads = List.of("0,1", "1,2"), marketEarnings = List.of(9, 14, 8), customerLoss = 4)

Returns 17.

Open markets 0 and 2. They are not directly connected, so neither market loses earnings. Their total is 9 + 8 = 17.

Example 2

maximumWeekendEarnings( villageCount = 2, roads = List.of("0,1"), marketEarnings = List.of(12, 11), customerLoss = 2)

Returns 19.

Opening both markets is optimal. Their final earnings are 12 - 2 = 10 and 11 - 2 = 9, giving a total of 19.

Example 3

maximumWeekendEarnings( villageCount = 5, roads = List.of("0,1", "0,2", "0,3", "0,4"), marketEarnings = List.of(25, 8, 8, 8, 8), customerLoss = 5)

Returns 32.

Open markets 1, 2, 3, and 4. None of these markets are directly connected to one another, so their total remains 8 + 8 + 8 + 8 = 32.

Example 4

maximumWeekendEarnings( villageCount = 1, roads = List.of(), marketEarnings = List.of(-7), customerLoss = 6)

Returns 0.

Leaving the only market closed is better than including its negative earnings.