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 翻译