← 返回题目列表

AtCoder · kupc2024_o

O. 普通开花算法

中文机器翻译题面 查看原题

配点 : 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