OI题库

【题目描述】

圣诞节到了，FireDancer准备做一棵大圣诞树。左图为圣诞树的一个简单结构。

这棵树被表示成一组被编号的结点和一些边的集合。结点从1到n编号。树的根永远是1。每个结点都有一个自身特有的数值，称为它的重。各个结点的重可能不同。对于一棵做完的树来说，每条边都有一个价值，若设这条边e连接结点i和结点j，且i为j的父结点(根是最老的祖先)，则该边的价值为(j的所有子孙及它自己的重之和)*（e的单位价值ce）。

现在FireDancer想造一棵树，使得树上所有边的总价值最小，并且所有的点都在树上，因为FireDancer喜欢大树。

【输入格式】

第一行两个整数n和m（0<=n,m<=50000），表示结点总数和可供选择的边数。

下面一行有n个整数，依次表示每个结点的重。

下面m行，每行有3个正整数a,b,c，表示结点a和结点b之间有一个单位价值为c的边可供你造树时选择。

输入中的所有数都小于2^16。

【输出格式】

若无解，输出“No Answer”，否则一个整数表示造树的最小价值。

【样例输入】

[样例输入1]

Chris.in

2 1

1 1

1 2 15

[样例输入2]

Chris.in

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

【样例输出】

【来源】

江苏省常州市高级中学 曹文培训图论练习题