[CTSC2004]网络改造network

HURRICANE 小组曾负责将校园内的计算机接入 Internet。他们先将计算机分组，把同一组的计算机连接到一台基层交换机上；随后设置一台对外的顶级网关交换机，并通过若干中间交换机，将所有交换机逐层连接到顶级网关交换机。

整个网络具有严格的层级结构：每台较低层的交换机只连接到一台较高层的交换机，而一台较高层的交换机可以连接多台较低层的交换机。因此，交换机之间的连接构成一棵树。

由于原有网络能够提供的服务有限，现在需要将其中一些交换机升级为核心交换机，并改造网络，使每台交换机要么是核心交换机，要么与某台核心交换机直接连接。受改造时间限制，最多只能将 $p$ 台交换机升级为核心交换机。

升级交换机和改造网络都会产生费用，总费用由以下两部分组成：

若两台交换机直接相连，则它们之间的距离为对应连接的网络长度；若两台交换机通过其他交换机间接相连，则它们之间的距离为唯一连接路径上所有边的网络长度之和。

请在升级的核心交换机数量不超过 $p$ 的条件下，求出最小总费用。如果没有任何交换机被升级为核心交换机，则由于其他交换机无法连接到核心交换机，规定此时的总费用为无穷大。

输入格式

第一行包含两个整数 $n$ 和 $p$ ，分别表示网络中的交换机数量和最多可以升级为核心交换机的数量。

接下来 $n$ 行，每行包含一个正整数 $c_i$ ，表示将编号为 $i$ 的交换机升级为核心交换机所需的费用。

接下来输入 $n-1$ 组整数 $i$ 、 $j$ 和 $d_{i,j}$ ，整数之间以空白字符分隔，表示编号为 $i$ 和 $j$ 的两台交换机直接相连，连接的网络长度为 $d_{i,j}$ 。

所有连接构成一棵树。输入中 $i$ 、 $j$ 的顺序不表示交换机之间的上下层关系。

第一行输出一个整数 $M$ ，表示最小总费用。

第二行输出一个整数 $p_0$ ，表示达到最小总费用时需要升级的核心交换机数量。如果有多个方案的总费用均为最小值，则输出其中核心交换机数量最少的方案对应的 $p_0$ 。

23
1

本题为 CTSC 2004 试题「网络改造」，题面与测试数据整理自 BZOJ。

23
1