seuOJ423 - 太优雅了

题目描述

给定一棵大小为 nn 的树，边有边权 ww。给定 mm 个点对 (x,y)(x,y)，定义这棵树的「不优雅值」为所有点对之间简单路径的长度总和。

请你任意选择树上的一条简单路径，将路径上的所有边权修改为 ⌊w2⌋\displaystyle\lfloor \frac{w}{2}\rfloor，使得「不优雅值」变得最小。输出最小的「不优雅值」。

输入格式

第一行两个正整数 n,m(2≤n,m≤2×105)n,m(2\le n,m\le 2\times 10^5)，表示树的大小和点对的数量。

接下来 n−1n-1 行，每行三个正整数 u,v,w(1≤u,v≤n,2≤w≤109)u,v,w(1\le u,v\le n,2\le w\le 10^9)，表示树上一条 uu 和 vv 之间权值为 ww 的边。

接下来 mm 行，每行两个正整数 x,y(1≤x,y≤n)x,y(1\le x,y\le n)，表示一组点对。

输出格式

输出一个非负整数，表示最小的「不优雅值」。

样例

输入样例 1：

5 2
1 2 2
1 5 8
2 3 4
2 4 6
3 5
3 4

输出样例 1：

15

数据范围与提示

保证输入数据为一棵树，且保证答案不会超过 101810^{18}。