Tree MST

题意翻译

给定一棵 $n$ 个节点的树,现有有一张完全图,两点 $x,y$ 之间的边长为 $w_x+w_y+dis_{x,y}$,其中 $dis$ 表示树上两点的距离。 求完全图的最小生成树。 $n \leq 2 \times 10^5$。

题目描述

[problemUrl]: https://cf17-final.contest.atcoder.jp/tasks/cf17_final_j りんごさんは $ N $ 頂点の木を持っています。 この木の $ N-1 $ 本の辺のうち $ i $ 番目の辺は頂点 $ A_i $ と頂点 $ B_i $ を繋いでおり、重みは $ C_i $ です。 また、頂点 $ i $ には $ X_i $ の重みがついています。 ここで $ f(u,v) $ を、「頂点 $ u $ から頂点 $ v $ までの距離」と「 $ X_u\ +\ X_v $ 」の和と定めます。 $ N $ 頂点の完全グラフ $ G $ を考えます。 頂点 $ u $ と頂点 $ v $ を繋ぐ辺のコストは $ f(u,v) $ です。 グラフ $ G $ の最小全域木を求めて下さい。

输入输出格式

输入格式


Input is given from Standard Input in the following format: ``` $ N $ $ X_1 $ $ X_2 $ $ ... $ $ X_N $ $ A_1 $ $ B_1 $ $ C_1 $ $ A_2 $ $ B_2 $ $ C_2 $ $ : $ $ A_{N-1} $ $ B_{N-1} $ $ C_{N-1} $ ```

输出格式


Print the cost of the minimum spanning tree of $ G $ .

输入输出样例

输入样例 #1

4
1 3 5 1
1 2 1
2 3 2
3 4 3

输出样例 #1

22

输入样例 #2

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

输出样例 #2

359

输入样例 #3

2
1000000000 1000000000
2 1 1000000000

输出样例 #3

3000000000

输入样例 #4

4
1 3 5 1
1 2 1
2 3 2
3 4 3

输出样例 #4

22

输入样例 #5

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

输出样例 #5

359

输入样例 #6

2
1000000000 1000000000
2 1 1000000000

输出样例 #6

3000000000

说明

### 制約 - $ 2\ \leq\ N\ \leq\ 200,000 $ - $ 1\ \leq\ X_i\ \leq\ 10^9 $ - $ 1\ \leq\ A_i,B_i\ \leq\ N $ - $ 1\ \leq\ C_i\ \leq\ 10^9 $ - 与えられるグラフは木である。 - 入力は全て整数である。 ### Problem Statement Ringo has a tree with $ N $ vertices. The $ i $ -th of the $ N-1 $ edges in this tree connects Vertex $ A_i $ and Vertex $ B_i $ and has a weight of $ C_i $ . Additionally, Vertex $ i $ has a weight of $ X_i $ . Here, we define $ f(u,v) $ as the distance between Vertex $ u $ and Vertex $ v $ , plus $ X_u\ +\ X_v $ . We will consider a complete graph $ G $ with $ N $ vertices. The cost of its edge that connects Vertex $ u $ and Vertex $ v $ is $ f(u,v) $ . Find the minimum spanning tree of $ G $ . ### Constraints - $ 2\ \leq\ N\ \leq\ 200,000 $ - $ 1\ \leq\ X_i\ \leq\ 10^9 $ - $ 1\ \leq\ A_i,B_i\ \leq\ N $ - $ 1\ \leq\ C_i\ \leq\ 10^9 $ - The given graph is a tree. - All input values are integers. ### Sample Explanation 1 頂点 $ 1 $ と $ 2 $ 、頂点 $ 1 $ と $ 4 $ 、頂点 $ 3 $ と $ 4 $ を繋ぐとそれぞれのコストは $ 5,8,9 $ となり、合計は $ 22 $ となります。 ### Sample Explanation 4 We connect the following pairs: Vertex $ 1 $ and $ 2 $ , Vertex $ 1 $ and $ 4 $ , Vertex $ 3 $ and $ 4 $ . The costs are $ 5 $ , $ 8 $ and $ 9 $ , respectively, for a total of $ 22 $ .