Problem : 70 - 植樹問題

Problem Statistics

Solved Member: 20　　Submission: 63　　User Tried: 20

Statement:

你想要種一棵假的樹，擺在學校門口。

這棵樹是由 n 個裝飾品所組成的，分別由 1 標號到 n ，以裝飾品 1 當做根插在泥土裡面，並且用竹竿往上連接其他裝飾品。你決定了非常久，終於決定了一些長得比較好看的連接方式。每個裝飾品 i 有他的重量 Wi，你擁有 m 條竹竿，這 m 條竹竿分別有與他相稱的 2 個點，你決定要用其中的 n-1 條竹竿來將所有的裝飾品連接成一棵樹。

正當你興致勃勃的想要植樹時，你發現了這項工作的難處。由於每個裝飾品有他的重量，如果上面的裝飾品重量和越重，則竹竿越難支撐。每條竹竿 j 有他的脆弱度 Cj。你發現，要往上接一條邊的難度恰好等於「Cj * j上面所有裝飾品的總重量」。

你希望「由下往上」來建造這一棵樹(也就是竹竿只能夠由下往上連接其他裝飾品)，並且你又希望這項工程的困難度是最小的。於是你決定寫個程式來計算最小的困難度會是多少。

Input:Output:

第 1 行有 n,m 兩個數字，代表裝飾品的數量和竹竿的數量。
第 2 行有 n 個數字，分別代表每一個裝飾品的重量 Wi。

後面 m 行每行有 3 個數字 A,B,Cj，代表可以用一條脆弱度為 Cj 的竹竿來連接 A 和 B 兩個裝飾品。

所有測資滿足：
0 ≤ n,m ≤ 50000
1 ≤ A,B ≤ n
Cj,Wi ≤ 65536

輸出一個數字，代表建造一棵樹最小的困難度。
如果沒辦法造出這棵樹請輸出"No Answer"(不含引號)。

Sample Input:Sample Output:

SAMPLE 1:
2 1
1 1
1 2 15

SAMPLE 2:
7 7
200 10 20 30 40 50 60
1 2 1
2 3 3
2 4 2
3 5 4
3 7 2
3 6 3
1 5 9

SAMPLE 1:
15

SAMPLE 2:
1210

HINT:

第2筆範例的圖示。

Source:

PKU 3013

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0-1	500ms	131072kb
0-2	500ms	131072kb
1-1	500ms	131072kb	10
1-2	500ms	131072kb
1-3	500ms	131072kb
2-1	500ms	131072kb	10
2-2	500ms	131072kb
3-1	500ms	131072kb	10
3-2	500ms	131072kb
4-1	500ms	131072kb	10
4-2	500ms	131072kb
5-1	500ms	131072kb	10
5-2	500ms	131072kb
6-1	1500ms	131072kb	10
6-2	1500ms	131072kb
7-1	1500ms	131072kb	10
7-2	1500ms	131072kb
8-1	1500ms	131072kb	10
8-2	1500ms	131072kb
9-1	1500ms	131072kb	10
9-2	1500ms	131072kb
10-1	1500ms	131072kb	10
10-2	1500ms	131072kb