P5793 [CTSC2004] Network Reconstruction.

The network originally built by the HURRICANE group consists of switches and the links between them. The switches are connected in levels. The highest one is the top gateway switch, and all other switches are connected to this gateway switch level by level. Note that any non-gateway switch is directly connected to exactly one switch at the next higher level, while any switch may be directly connected to several switches at the next lower level. Recently, because the original network services are limited, some switches in the network (including the gateway switch) need to be upgraded to core switches. Due to limited time, at most $p$ switches (including $p$) can be upgraded to core switches, and all remaining switches must be directly connected to these core switches by reconstructing the network links. However, both upgrading switches and reconstructing links cost money. Please provide a reconstruction plan such that after the upgrade, every switch is either a core switch or is directly connected to a core switch, and the total cost of reconstruction is minimized.

Your program must produce output that satisfies the requirements based on the given input: - The input includes the network topology, the cost to upgrade each switch in the network, the cost to reconstruct links, and the maximum number $p$ of switches that can be upgraded. - Based on the input, you must find an upgrade plan such that the number of core switches after upgrading does not exceed the given maximum $p$, and the total cost is minimized. - The total cost consists of two parts: - One part is the cost required to upgrade switches to core switches, which is the sum of the upgrade costs of all switches that are upgraded. - The other part is the cost required to reconstruct the network, which is the sum of the network path distances from every non-upgraded switch to its nearest core switch. - **Note:** If no switch in the network is upgraded to a core switch, since no switch can be connected to a core switch, we define the total cost in this case to be infinity.

The first line contains two positive integers $n(n \leq 400)$ and $p$, representing the number of switches in the network (switches are numbered from $1$ to $n$) and the maximum number of switches that can be upgraded. The next $n$ lines each contain a positive integer $c_i$, representing the cost to upgrade switch $i$ to a core switch. The next $n-1$ lines each contain three positive integers $i$, $j$, and $d_{i,j}(d_{i,j}

The first line of output contains an integer $M$, representing the minimum total cost of your plan. The next line contains an integer $p_0$, representing the number of switches that need to be upgraded to core switches in your plan.

#### Sample Explanation  #### Scoring Method There are ten test points in this problem, and each test point is worth $10\%$ of the total score. For each test point, if your answer is correct, you will get the full score for that test point; otherwise, you will get $0$ points. Note that in the testdata of this problem, there are $8$ cases where $n$ does not exceed $180$. Translated by ChatGPT 5