NC20396. [SHOI2004]MST 最小生成树
描述
给定一个筒单图G=<V.E.W>，V为定点集合，E为边的集合（无重边，即任意两个顶点之间至多只有一条边)，W为定义在E上的权函数（值为整数)。给出其上的一棵生成树T，现在要求用最小的代价修改W，使得T是G上的一棵最小生成树（一个图可以有多棵最小生成树，只要T的边权和最小即可)。对于任意一条边e∈E修改方法为：
- 增加e的权值，即令W′(e)=W(e)+Δ(e)，则修改该边的代价为\Δ(e)
- 减小e的权值，即令W′(e)=W(e)−Δ(e)，则修改该边的代价为Δ(e)
- 不改变e的权，即W′(e)=W(e)，修改代价为Δ(e)=0。
请注意：修改后的权函数W'的值域也为整数。
总的修改代价记为
输入描述
第一行为N、M，其中 表示顶点的数目， 表示边的数目。顶点的编号为1、2、3、……、N-1、N。接下来的M行，每行三个整数Ui，Vi，Wi，表示顶点Ui与Vi之间有一条边，其权值为Wi。所有的边在输入中会且仅会出现一次。再接着N-1行，每行两个整数Xi、Yi，表示顶点Xi与Yi之间的边是T的一条边。
输出描述
输出最小权值
示例1
输入:
6 9 1 2 2 1 3 2 2 3 3 3 4 3 1 5 1 2 6 3 4 5 4 4 6 7 5 6 6 1 3 2 3 3 4 4 5 4 6
输出:
8
说明:
【样例说明】边(4,6)的权由7修改为3，代价为4
边(1,2)的权由2修改为3，代价为1
边(1,5)的权由1修改为4，代价为3
所以总代价为4+1+3=8
修改方案不唯一。