结果比较方式为全文比较（过滤行末空格及文末换行）。

题目描述

程老师分管一片值守区域。区域里一共有 $n$ 个节点，编号 $1$ 到 $n$，其中 $1$ 号是总控中心。节点之间铺设了 $n-1$ 条链路，铺法保证任意两个节点之间恰有一条通路（沿链路走，不重复经过任何节点）。

总控中心把命令一级一级往下传。除 $1$ 号以外，每个节点都有唯一的上级：从它出发，沿唯一的那条通路走向 $1$ 号，紧邻它、且更靠近 $1$ 号的那个节点就是它的上级；反过来，若节点 $x$ 的上级是 $y$，就说 $x$ 是 $y$ 的下级。除 $1$ 号以外，没有下级的节点称为末梢节点。

一次封锁行动中，程老师可以选定任意若干个节点封锁（一个节点都不封也可以），封锁节点 $i$ 的代价是 $w_i$。行动有一条硬性要求：每一条从某个末梢节点到总控中心的通路上（通路包含两端节点在内），至少要有一个节点被封锁。

在满足这条要求的前提下，程老师希望总代价尽可能小；如果有多套封锁方案的总代价相同，他希望封锁的节点数尽可能少。请你给出这套封锁方案的总代价与封锁的节点数。

输入格式

从文件 blockade.in 中读入数据。

• 第一行一个整数 $n$；
• 第二行 $n$ 个整数 $w_1, w_2, \dots, w_n$，其中 $w_i$ 表示封锁节点 $i$ 的代价；
• 接下来 $n-1$ 行，每行两个整数 $u, v$，表示节点 $u$ 与节点 $v$ 之间有一条链路。

输出格式

输出到文件 blockade.out 中。

输出一行两个整数，中间用一个空格隔开：最小的总代价，以及在总代价最小的前提下最少的封锁节点数。

样例

5
10 5 4 3 2
1 2
1 3
3 4
3 5

9 2

样例 1 解释

节点 $2, 4, 5$ 都没有下级，是仅有的三个末梢节点（$1$ 号是总控中心，不算末梢），因此通路 $2 \to 1$、$4 \to 3 \to 1$、$5 \to 3 \to 1$ 都必须被覆盖。若只封锁 $1$ 号，三条通路一条不落，代价 $10$，封锁 $1$ 个节点；若改封锁 $3$ 号，代价 $4$，通路 $4 \to 3 \to 1$ 与 $5 \to 3 \to 1$ 一并被覆盖，比分别封锁 $4$ 号与 $5$ 号（$3 + 2 = 5$）更划算。剩下通路 $2 \to 1$ 上只有 $2$ 号与 $1$ 号两个节点，封锁 $2$ 号代价 $5$，封锁 $1$ 号代价 $10$，取 $2$ 号。于是封锁 $2$ 号与 $3$ 号，总代价 $5 + 4 = 9$，封锁 $2$ 个节点，比只封锁 $1$ 号的代价 $10$ 更低。

2
3 7
1 2

3 1

样例 2 解释

区域里只有两个节点：$2$ 号的上级是 $1$ 号，而 $2$ 号没有下级，所以 $2$ 号是唯一的末梢节点，通路 $2 \to 1$ 上只有 $1$ 号与 $2$ 号这两个节点。封锁 $2$ 号代价 $7$，封锁 $1$ 号代价 $3$，两种方案都只封锁 $1$ 个节点，取代价较小的那种，于是总代价为 $3$、封锁节点数为 $1$。

数据范围

对于所有测试数据，保证：

• $2 \le n \le 10^5$，$1 \le w_i \le 10^4$；
• 链路连接的两个节点编号不同，且任意两个节点之间恰有一条通路。

各测试点的约束如下：

• 特殊性质 A：每个节点至多只有一个下级节点。
• 特殊性质 B：所有节点的封锁代价都相等。