Easy MST

Time limit: 5.0s , Memory limit: 256M , Points: 1

Cho cây $T$ ~T~ gồm $n$ ~n~ đỉnh, các đỉnh được đánh số từ $1$ ~1~ đến $n$ ~n~ và các cạnh được đánh số từ $1$ ~1~ đến $n-1$ ~n-1~. Cạnh thứ $i$ ~i~ của cây nối hai đỉnh $u_i$ ~u_i~ và $v_i$ ~v_i~ với trọng số $w_i$ ~w_i~. Mỗi đỉnh $x$ ~x~ của cây đều được gán một trọng số $a_x$ ~a_x~.

Hàm $d(u,v)$ ~d(u,v)~ được định nghĩa là độ dài đường đi ngắn nhất giữa hai đỉnh $u$ ~u~ và $v$ ~v~ trên cây.

Hàm $f(u,v)$ ~f(u,v)~ được định nghĩa như sau:

$f(u,v)=d(u,v)+a_u+a_v$

Xét đơn đồ thị $G$ ~G~ bao gồm $n$ ~n~ đỉnh và $\frac{n(n-1)}{2}$ ~\frac{n(n-1)}{2}~ cạnh, giữa hai đỉnh $u$ ~u~ và $v$ ~v~ $(u \neq v)$ ~(u \neq v)~ của đồ thị $G$ ~G~ có trọng số $f(u,v)$ ~f(u,v)~. Bạn hãy tìm độ dài cây khung nhỏ nhất của $G$ ~G~.

Input

Dòng đầu tiên chứa số nguyên $n$ ~n~ $(2 \le n \le 2 \times 10^5)$ ~(2 \le n \le 2 \times 10^5)~.
Dòng thứ hai chứa $n$ ~n~ số nguyên $a_i$ ~a_i~ $(1 \le a_i \le 10^9)$ ~(1 \le a_i \le 10^9)~.
$n-1$ ~n-1~ dòng tiếp theo, dòng thứ $i$ ~i~ chứa ba số nguyên $u_i,v_i$ ~u_i,v_i~ và $w_i$ ~w_i~ mô tả cạnh thứ $i$ ~i~ của cây $(1 \le u_i,v_i \le n$ ~(1 \le u_i,v_i \le n~ $;$ ~;~ $1 \le w_i \le 10^9)$ ~1 \le w_i \le 10^9)~.
Dữ liệu đảm bảo các cạnh đã cho tạo thành một cây hợp lệ.

Output

In ra độ dài cây khung nhỏ nhất của đồ thị $G$ ~G~.

Examples

Sample Input 1

Sample Output 1

Sample Input 2

6
44 23 31 29 32 15
4 5 8
2 1 10
6 4 15
3 1 12
1 4 16

Sample Output 2

Notes

Trong ví dụ đầu tiên, các giá trị $f(u,v)$ ~f(u,v)~ như sau:

$f(1,2)=5$ ~f(1,2)=5~
$f(1,3)=9$ ~f(1,3)=9~
$f(1,4)=8$ ~f(1,4)=8~
$f(2,3)=10$ ~f(2,3)=10~
$f(2,4)=9$ ~f(2,4)=9~
$f(3,4)=9$ ~f(3,4)=9~

Comments

0

T-JUN-8337 commented on Feb. 3, 2025, 3:38 p.m.

comment này spoil thuật: sử dụng thuật prim và dựng cây centroid để update và truy vấn khoảng cách (hàm f())

Link