AT_kupc2024_o Ordinary Blossom Algorithm

有一棵以 $1$ 号结点为根的 $N$ 个结点的有根树，结点编号为 $1$ 到 $N$。第 $i$ 条边连接结点 $A_i$ 和 $B_i$。 每个结点都有一个权值，第 $v$ 个结点的权值为 $W_v$。 你的目标是通过进行如下操作任意次数，最终将树收缩为只包含结点 $1$ 的树。 - 选择从根出发的一条路径，将路径上所有的边进行缩约，并把路径结束点作为新的根。新的根的权值为该路径上所有结点的权值之和 $S$，并将 $S$ 加入到总成本中。 请在所有能以最少操作次数完成目标的方案中，求出可能的最小代价和最大代价，记为 $C_{\min}$ 和 $C_{\max}$。

输入通过标准输入给出，格式如下： > $N$ > $A_1\ B_1$ > $A_2\ B_2$ > $\vdots$ > $A_{N-1}\ B_{N-1}$ > $W_1\ W_2\ \cdots\ W_N$

请输出以空格分隔的两个整数 $C_{\min}$ 和 $C_{\max}$。 > $C_{\min}\ C_{\max}$

### 样例解释 1 将树收缩为 $1$ 个结点所需的最小操作次数是 $2$。 如果第一次选择的路径是 $1-2-4$，则新的树只剩下新根（设为结点 $5$）和结点 $3$，新根权值为 $S=50$。然后再选路径 $5-3$，此时树最终变为只有权值为 $S=51$ 的一个结点，总花费为 $50+51=101$，这是用 $2$ 次操作完成时的最大代价。 相反，如果第一次选择 $1-3$（新根设为结点 $5$），然后选择 $5-2-4$，总花费为 $21+51=72$，是 $2$ 次操作时的最小代价。 ### 数据范围 - 所有输入为整数 - $2 \le N \le 2 \times 10^5$ - $1 \le A_i, B_i \le N$ - $1 \le W_v \le 10^8$ - 输入保证构成一棵树 由 ChatGPT 5 翻译