Tree MST
题意翻译
给定一棵 $n$ 个节点的树，现有有一张完全图，两点 $x,y$ 之间的边长为 $w_x+w_y+dis_{x,y}$，其中 $dis$ 表示树上两点的距离。
求完全图的最小生成树。
$n \leq 2 \times 10^5$。
题目描述
[problemUrl]: https://atcoder.jp/contests/cf17-final/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 $ の最小全域木を求めて下さい。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ 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} $
输出格式
グラフ $ 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说明
### 制約
- $ 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 $
- 与えられるグラフは木である。
- 入力は全て整数である。
### Sample Explanation 1
頂点 $ 1 $ と $ 2 $、頂点 $ 1 $ と $ 4 $、頂点 $ 3 $ と $ 4 $ を繋ぐとそれぞれのコストは $ 5,8,9 $ となり、合計は $ 22 $ となります。