题目描述

现有一棵无向、无根的树，树中有 $n$ 个节点，按从 $0$ 到 $n - 1$ 编号。给你一个整数 $n$ 和一个长度为 $n - 1$ 的二维整数数组 $edges$ ，其中 $edges[i] = [a_i, b_i]$ 表示树中节点 $a_i$ 和 $b_i$ 之间存在一条边。

每个节点都关联一个价格。给你一个整数数组 $price$ ，其中 $price[i]$ 是第 $i$ 个节点的价格。

给定路径的 价格总和 是该路径上所有节点的价格之和。

另给你一个二维整数数组 $trips$ ，其中 $trips[i] = [start_i, end_i]$ 表示您从节点 $start_i$ 开始第 $i$ 次旅行，并通过任何你喜欢的路径前往节点 $end_i$ 。

在执行第一次旅行之前，你可以选择一些 非相邻节点 并将价格减半。

输出执行所有旅行的最小价格总和。

输入格式

第一行两个空格隔开的整数，表示树的点数 n 和 旅行的次数 m；

第二行至第 n 行，每行两个空格隔开的整数表示 $a_i, b_i$；

第 n+1 行共 n 个空格隔开的整数表示 $price_i$；

接下来 m 行，每行两个空格隔开的整数表示 $start_i, end_i$。

输出格式

一行一个整数表示答案。

样例

示例 1：

4 3
0 1
1 2
1 3
2 2 10 6
0 3
2 1
2 3

23

解释：

上图表示将节点 2 视为根之后的树结构。第一个图表示初始树，第二个图表示选择节点 0 、2 和 3 并使其价格减半后的树。

第 1 次旅行，选择路径 [0,1,3] 。路径的价格总和为 1 + 2 + 3 = 6 。

第 2 次旅行，选择路径 [2,1] 。路径的价格总和为 2 + 5 = 7 。

第 3 次旅行，选择路径 [2,1,3] 。路径的价格总和为 5 + 2 + 3 = 10 。

所有旅行的价格总和为 6 + 7 + 10 = 23 。可以证明，23 是可以实现的最小答案。

示例 2：

2 1
0 1
2 2
0 0

1

解释：

上图表示将节点 0 视为根之后的树结构。第一个图表示初始树，第二个图表示选择节点 0 并使其价格减半后的树。

第 1 次旅行，选择路径 [0] 。路径的价格总和为 1 。

所有旅行的价格总和为 1 。可以证明，1 是可以实现的最小答案。

提示：

• $1 <= n <= 50$
• $edges.length == n - 1$
• $0 <= a_i, b_i <= n - 1$
• $edges$ 表示一棵有效的树
• $price.length == n$
• $price[i]$ 是一个偶数
• $1 <= price[i] <= 1000$
• $1 <= trips.length <= 100$
• $0 <= start_i, end_i <= n - 1$