U367133 「审判-惩戒骑士」

 > 1350年10月，弗萨克帝国空袭鲁恩王国首都贝克兰德，翌日鲁恩对弗萨克宣战，同年12月鲁恩国王乔治三世晋升“黑皇帝”失败陨落，其长子哥温顿二世继位。 乔治三世的陨落为鲁恩王国的政治局势带来了巨大变化，比如休 · 迪尔查终于进入了官方正式体系，并成为了情报机构高层。 战争还在继续，休在晋升成为「审判者」序列五「惩戒骑士」之后得到了更加强大的战斗能力。她在首都贝克兰德调查了解了一些弗萨克帝国派遣的间谍组织窝点的分布，做出今晚立即实施围剿的重大决定。

整个间谍组织共占有 $n$ 栋楼房，由 $m$ 条具有传送能力的双向通道相连。似乎是为了确保人员来往不会迷路，这些通道并**不会构成环**。 休可以在一栋楼房使用「惩戒骑士」的非凡能力，在这里释放实体化的「规则」方便战斗。「规则」的力量可以**沿着空间魔法筑成的通道传播至另一房屋（仅从「规则」所在之处传播一层）。** 休不希望“收网”有任何疏漏，因此她要让间谍组织的**所有楼房**受到限制。 间谍组织在每栋楼房安排了不同程度的保护措施，因此休每到一栋楼房都有一定的**危险程度，记为 $a_i$。** 休此次行动的**危险值**为**走过的所有楼房的危险程度之和**。 值得注意的是，由于休从佛尔思 · 沃尔那里~~偷~~借来了「莱曼诺的旅行笔记」，她可以使用多次传送能力，意味着她可以瞬间抵达任何房屋，**无需路过中途的其他点**。 休需要你帮她评估两个方案： 1. **释放「规则」个数最少**的方案； 2. **危险值最小**的方案。 对于第一个方案，请你告诉休：**释放「规则」的个数是多少？** 对于第二个方案，请你告诉休：**危险值是多少？** ### 形式化题面 一片 $n$ 点 $m$ 边的森林，选择一个节点可支配其所有相邻节点，求支配所有节点的两个方案，分别使得所选点数最小和所选节点权值和最小，并分别输出这两个最小值。

输入共 $m+2$ 行。 第一行两个整数 $n$ 和 $m$。 第二行 $n$ 个整数 $a_1,a_2,\dots a_n$。 第 $3$ 到 $m+2$ 行，第 $i+2$ 行两个整数 $u_i,v_i$，表示有一条通道连接编号 $u_i,v_i$ 的两栋楼房。**保证没有重边和自环**。

输出共 $2$ 行。 第一行一个整数，表示「规则」的最少个数。 第二行一个整数，表示危险值的最小值。

对于 $20\%$ 的数据，保证 $n\leq20$。 对于另外 $20\%$ 的数据，保证 $a_i=1$。 对于另外 $20\%$ 的数据，保证 $m=n-1$。 对于 $100\%$ 的数据，$1\leq u_i,v_i\leq n\leq 10^5,0\leq a_i \leq 10^9$。