AT_kupc2014_f テレパシー

在二维平面上有 $N$ 只狐狸。第 $i$ 只狐狸坐标是 $(x_i,y_i)$。 狐狸可以使用他们的特殊能力与远处的朋友交流。 设两只狐狸的力量强度为 $p_1$ 和 $p_2$，当狐狸之间的欧几里得距离为 $D$ 时,如果 $p_1+p_2 \ge D$，他们可以保持联系。第 $i$ 只狐狸和第 $j$ 只狐狸之间的欧几里得距离是 $\sqrt{\left(x_{i}-x_{j}\right)^{2}+\left(y_{i}-y_{j}\right)^{2}}$。第 $i$ 只狐狸初始力量是 $d_i$，每支付一次费用 $c_i$，可以增加 $1$ 点力量。 在 $N$ 个狐狸之间创建一个联系网络 $T$。$T$ 是一棵树，树上有 $N$ 只狐狸。它由 $(u_1,v_1),\dots ,(u_{N-1},v_{N-1})$ 共 $N-1$ 个边组成，$(u_i,v_i)$ 表示连接编号为 $u_i , v_i$ 的两只狐狸，只有编号为 $u_i , v_i$ 的两只狐狸可以互相通信。要求树上任意两只狐狸都能够互相通信（允许中转）。 找出当狐狸的力量强度增加以使所需的成本尽可能小时，搭建树 $T$ 的成本是多少。

第一行一个整数 $N$。 第 $2 \sim N+1$ 行，输入 $x_i,y_i$。 第 $N+1 \sim 2 \times N+1$ 行，输入 $d_i,c_y$。 第 $2 \times N+2 \sim 3 \times N$ 行，输入 $u_i,v_i$

一个整数，表示构造 $T$ 的最小值。

- $1 \le N \le 10^3$ - $\left | x_i \right | ,\left | y_i \right | \le 10^3$ - $x_i \ne y_i$ - $1 \le d_i,c_i \le 10^3$ - $1 \le u_i,v_i \le N$ - $T$ 保证是一棵树。 - 以上数据均为整数。 #### 原题给出的其他东西 - 最好将第 $2$ 只狐狸的力量增加 $3$ 倍。