← 返回题目列表

AtCoder · kupc2014_f

F. 心灵感应

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

在二维平面上 N 有狐狸。 i 狐狸的 x 坐标是 x_i y 坐标是 y_i 。从

狐狸可以使用特殊的力量与远方的朋友进行交流。 两只狐狸的实力 p_1, p_2 狐狸之间的欧几里得距离是 当 D 时, p_1 + p_2 \geq D 然后他们就可以保持联系。 然而,i 与狐狸 j 狐狸的欧几里得距离是 \sqrt{ (x_i - x_j) ^ {2} + (y_i - y_j) ^ {2} } 。从 i 狐狸之力的强度初始为 d_i ,成本 每次支付 c_i 即可将强度增加1。

在这里, N 狐狸之间的通信网络 考虑创建 T 。 T 表示 N 顶部有一只狐狸全域木和N - 1 边缘 它由 (u_1, v_1), …, (u_{N - 1}, v_{N - 1}) 组成。即 第 i = 1, …, N-1 关于 u_i 与狐狸 v_i 只狐狸由一条边连接。 联系网络 要创建 T , T 中的任何边 (u, v) 从 u与狐狸 v狐狸需要能够沟通。 即使你可以通过其他狐狸联系到他们, u 与狐狸 v 狐狸必须直接接触。

当狐狸的力量增加到尽可能小的所需成本时, 求出制造 T 的成本。

入力形式

输入按以下格式给出。

N
x_1 y_1
…
x_N y_N
d_1 c_1
…
d_N c_N
u_1 v_1
…
u_{N-1} v_{N-1}

出力形式

输出在一行中创建接触网络所需的最小成本。

制約

  • 1 \leq N \leq 10^3
  • |x_i|, |y_i| \leq 10^3
  • (x_i, y_i) 是不同的。
  • 1 \leq d_i, c_i \leq 10^3
  • 1 \leq u_i, v_i \leq N
  • T 保证是一棵树。
  • 所有输入值都是整数。 第

入出力例

入力例1

3
0 0
3 0
-3 0
1 100
1 3
1 3
1 2
1 3

出力例1

6

第二只狐狸和第三只狐狸的力量最好各增加1。

入力例2

3
0 0
3 0
-3 0
1 5
1 3
1 3
1 2
1 3

出力例2

5

最好将第一只狐狸的力量增加1。

入力例3

4
0 0
7 0
-7 0
0 5
2 5
2 1
2 1
2 10
1 2
1 3
1 4

出力例3

9

最好将第一只狐狸的力量增加1,第二、第三只狐狸的力量各增加2。

入力例4

3
0 0
3 4
6 0
1 1
1 1
1 1
1 2
2 3

出力例4

3

第二只狐狸的力量最好增加3点。