配点 : 100 点
問題文
1 减去 N 的顶点 植根于 1 植根于 N 我有一棵有根的顶点树。 这是连接i 第一条边是顶点 A_i 与边缘 B_i 的边。 编号至
每个顶点都有一个权重, v 的权重是 W_v 。
您的目标是执行以下任意次数,最后 1 使其成为一棵由顶点组成的树。
- 从根延伸的路径 1 选择一个并收缩所有包含的边以形成新的根。那么,新根的权重就是路径中包含的顶点权重之和 S 并将其设置为成本。 添加 S 。
找出可最小化实现目标的操作数量的操作中的最小和最大成本。
制約
- 所有输入均为整数
- 2 \le N \le 2 \times 10^5
- 1 \le A_i,B_i \le N
- 1 \le W_v \le 10^8
- 作为输入给出的图是一棵树。
入力
输入是按以下格式从标准输入给出的。
N
A_1 B_1
\vdots
A_{N-1} B_{N-1}
W_1 W_2 \cdots W_N
出力
找出以最少的操作数实现目标的操作序列中的最小和最大成本。 C_{\min},C_{\max} 。
2 按此顺序输出值,用空格分隔。
C_{\min} C_{\max}
入力例 1
4 1 2 1 3 2 4 20 25 1 5
出力例 1
72 101
1 创建顶点树的最少操作数为 2 次。
先通过 选择 1-2-4 创建一个新的根(顶点 5 ) 和顶点 3 现已连接,S=50 是根的权重。然后是路径 如果选择 5-3 ,树将被加权。 S=51 可以得到第 1 操作将在顶点结束。此时的成本为 取 50+51=101 变为 通过 2 次内实现目标的最大成本。
另外,路径 1-3 (新根到顶点 5 ),路径 如果按照 5-2-4 的顺序操作,则成本为 取在 21+51=72 变为 通过2 次内实现目标的最小成本。
入力例 2
10 2 4 3 8 7 9 6 3 2 1 9 5 9 6 3 10 9 2 19359725 62617217 96402215 25620070 46288197 40930485 37441368 32164537 69968419 79525817
出力例 2
1525009090 2231445426