A - Weighting a Tree Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君は N 頂点の木を持っています。頂点には 1 から N の番号が付けられています。木には N - 1 本の辺があり、辺にも 1 から N-1 の番号が付けられています。i 番目 (1 \leq i \leq N-1) の辺は頂点 u_i と頂点 v_i を結んでおり、正の整数の 重み w_i が定められています。

高橋君は、各辺 i に正の整数（1 以上の整数）の 乗数 r_i を設定しようとしています。辺 i に乗数 r_i を設定したとき、その辺の コスト は w_i \times r_i です。

乗数の設定は、以下の条件を満たさなければなりません：

  • 木の任意の相異なる 2 頂点の組 \{a, b\} について、頂点 a から頂点 b への（木上で一意に定まる）パスに含まれる辺の本数を k とし、そのパスが順に辺番号 e_1, e_2, \ldots, e_k を通るとする。このとき、

r_{e_1} + r_{e_2} + \cdots + r_{e_k} \leq k^2

が成り立たなければならない。

条件を満たす乗数の設定は必ず存在します。例えば、すべての辺の乗数を 1 に設定すると、任意のパスについて乗数の合計は k であり、k \geq 1 のとき k \leq k^2 が成り立つため、条件を満たします。

条件を満たすすべての設定の中で、全辺のコストの合計

\sum_{i=1}^{N-1} w_i \times r_i

の最小値を求めてください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq u_i, v_i \leq N
  • u_i \neq v_i
  • 1 \leq w_i \leq 10^9
  • 入力で与えられるグラフは木である
  • 入力はすべて整数である
  • 答えは 2^{63} - 1 以下である

入力

N
u_1 v_1 w_1
u_2 v_2 w_2
\vdots
u_{N-1} v_{N-1} w_{N-1}
  • 1 行目には、頂点の数を表す整数 N が与えられる。
  • 続く N - 1 行のうち i 行目 (1 \leq i \leq N-1) では、i 番目の辺が結ぶ 2 つの頂点の番号 u_i, v_i と重み w_i が空白区切りで与えられる。

出力

条件を満たすように各辺の乗数（正の整数）を設定したとき、全辺のコストの合計の最小値を 1 行で出力せよ。

入力例 1

4
1 2 3
2 3 5
2 4 2

出力例 1

10

入力例 2

5
1 2 10
1 3 1
1 4 7
1 5 4

出力例 2

22

入力例 3

12
1 2 8
1 3 6
2 4 15
2 5 3
3 6 20
3 7 5
4 8 11
5 9 9
6 10 2
7 11 14
7 12 1

出力例 3

94

入力例 4

30
1 2 100
1 3 200
2 4 50
2 5 75
3 6 125
3 7 60
4 8 90
4 9 30
5 10 45
5 11 85
6 12 110
6 13 95
7 14 40
7 15 70
8 16 150
9 17 20
10 18 130
11 19 55
12 20 65
13 21 35
14 22 25
15 23 115
16 24 105
17 25 10
18 26 140
19 27 80
20 28 120
21 29 5
22 30 160

出力例 4

2390

入力例 5

2
1 2 1000000000

出力例 5

1000000000

Score : 200 pts

Problem Statement

Takahashi has a tree with N vertices. The vertices are numbered 1 to N. The tree has N - 1 edges, also numbered 1 to N-1. The i-th edge (1 \leq i \leq N-1) connects vertex u_i and vertex v_i, and has a positive integer weight w_i.

Takahashi wants to assign a positive integer (an integer \geq 1) multiplier r_i to each edge i. When a multiplier r_i is assigned to edge i, the cost of this edge is w_i \times r_i.

The assignment of multipliers must satisfy the following condition:

  • For any pair of distinct vertices \{a, b\} in the tree, let k be the number of edges on the (unique) path between vertex a and vertex b, and let the path traverse edges e_1, e_2, \ldots, e_k in order. Then,

r_{e_1} + r_{e_2} + \cdots + r_{e_k} \leq k^2

must hold.

An assignment satisfying the condition always exists. For example, if we set the multipliers of all edges to 1, the sum of multipliers for any path of length k is k, and since k \leq k^2 holds for k \geq 1, this assignment satisfies the condition.

Find the minimum possible total cost of all edges,

\sum_{i=1}^{N-1} w_i \times r_i

among all assignments that satisfy the condition.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq u_i, v_i \leq N
  • u_i \neq v_i
  • 1 \leq w_i \leq 10^9
  • The given graph is a tree.
  • All input values are integers.
  • The answer is at most 2^{63} - 1.

Input

N
u_1 v_1 w_1
u_2 v_2 w_2
\vdots
u_{N-1} v_{N-1} w_{N-1}
  • The first line contains an integer N, representing the number of vertices.
  • In the following N - 1 lines, the i-th line (1 \leq i \leq N-1) contains three space-separated integers u_i, v_i, and w_i, representing the vertices u_i and v_i connected by the i-th edge, and its weight w_i.

Output

Print the minimum possible total cost of all edges when the multipliers (positive integers) are assigned to satisfy the condition, in a single line.

Sample Input 1

4
1 2 3
2 3 5
2 4 2

Sample Output 1

10

Sample Input 2

5
1 2 10
1 3 1
1 4 7
1 5 4

Sample Output 2

22

Sample Input 3

12
1 2 8
1 3 6
2 4 15
2 5 3
3 6 20
3 7 5
4 8 11
5 9 9
6 10 2
7 11 14
7 12 1

Sample Output 3

94

Sample Input 4

30
1 2 100
1 3 200
2 4 50
2 5 75
3 6 125
3 7 60
4 8 90
4 9 30
5 10 45
5 11 85
6 12 110
6 13 95
7 14 40
7 15 70
8 16 150
9 17 20
10 18 130
11 19 55
12 20 65
13 21 35
14 22 25
15 23 115
16 24 105
17 25 10
18 26 140
19 27 80
20 28 120
21 29 5
22 30 160

Sample Output 4

2390

Sample Input 5

2
1 2 1000000000

Sample Output 5

1000000000