【题目描述】

有一棵无根树，共有 $n$ 个节点，编号为 $0$ 到 $n-1$, 每个节点有一个价格，$price_i$ 表示第 $i$ 个节点的价格（$price_i$ 为偶数）。

现在有 $m$ 次旅行，第 $i$ 次旅行从节点 $u_i$ 出发到节点 $v_i$，每次旅行的价格总和定义为该次旅行所经过简单路径上的所有节点的价格之和。

在第一次旅行开始前，你可以选择任意多个不相邻的节点（即选择的节点之间不能有边直接相连），并将这些节点的价格减半。 你的目标是最小化所有旅行的价格总和。请你输出这个最小值。

【输入格式】

第一行一个整数 $n$，表示树的节点数。

接下来 $n-1$ 行，每行两个整数 $a, b$，表示树中有一条连接 $a$ 和 $b$ 的边。

接下来一行 $n$ 个整数，表示 $price_0, price_1, \dots, price_{n-1}$。

接下来一行一个整数 $m$，表示旅行的次数。

接下来 $m$ 行，每行两个整数 $u, v$，表示一次从 $u$ 到 $v$ 的旅行。

【输出格式】

一个整数，表示所有旅行价格总和的最小值。

【样例 1】

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

23

【样例 1 解释】

初始价格：节点 $price_0=2,price_1=2,price_2=10,price_3=6$
选择不相邻的节点 $0,2,3$ 减半后：$price_0=1,price_1=2,price_2=5,price_3=3$。
三次旅行：

• $0→3$ 价格和 $= 1+2+3 = 6$

• $2→1$ 价格和 $= 5+2 = 7$

• $2→3$ 价格和 $= 5+2+3 = 10$

  总和 $= 6+7+10 = 23$，可以证明这是最小值。

【样例 2】

2
0 1
2 2
1
0 0

1

【样例解释2】

初始价格：节点 $price_0=2,price_1=2$

选择节点 $0$ 减半后：$price_0=1$。

$0→0$ 价格和 $= 1$，若选择 $1$ 节点减半 $0→0$ 价格和 $=2$，故最小值为 $1$

【数据规模与约定】

对于 $100\%$ 的数据满足:

• $1 \le n \le 50$
• $0 \le a, b \le n-1$ 且输入保证是一棵树
• $price$ 长度为 $n$，$1 \le price_i \le 1000$，且 $price[i]$ 为偶数
• $1 \le m \le 100$
• $0 \le u_i, v_i \le n-1$