CF1061E Politics

有 $n$ 个城市。 两位候选人正在竞争总统职位。选举将在未来举行，两位候选人都已经规划好了如何用道路连接这些城市。每份规划都只使用 $n-1$ 条道路连接所有城市。也就是说，每份规划都可以看作是一棵树。两位候选人还分别指定了他们心目中的首都（第一位候选人选择第 $x$ 个城市，第二位候选人选择第 $y$ 个城市），这两个城市可以相同也可以不同。 每个城市都有建设港口的潜力（每个城市最多只能建一个港口）。在第 $i$ 个城市建设港口可以获得 $a_i$ 的收益。然而，每位候选人都有自己的具体要求。要求的形式如下： - $k$ $x$，表示候选人希望在他所选树（以他选择的首都为根）的第 $k$ 个城市的子树内，恰好建设 $x$ 个港口。 请你计算，在满足两位候选人所有要求的前提下，最多可以获得多少收益。如果无法满足所有要求，则输出 $-1$。 另外保证，每位候选人都对自己选择的首都提出了港口建设要求。

第一行包含整数 $n$、$x$ 和 $y$（$1 \le n \le 500$，$1 \le x, y \le n$），分别表示城市数量、第一位候选人选择的首都和第二位候选人选择的首都。 第二行包含 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 100\,000$），表示在对应城市建设港口可获得的收益。 接下来 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \ne v_i$），表示第一位候选人的树中的一条边。 再接下来 $n-1$ 行，每行包含两个整数 $u'_i$ 和 $v'_i$（$1 \le u'_i, v'_i \le n$，$u'_i \ne v'_i$），表示第二位候选人的树中的一条边。 接下来一行包含整数 $q_1$（$1 \le q_1 \le n$），表示第一位候选人的要求数量。 接下来 $q_1$ 行，每行包含两个整数 $k$ 和 $x$（$1 \le k \le n$，$1 \le x \le n$），表示城市编号和在其子树内需要建设的港口数量。 再接下来一行包含整数 $q_2$（$1 \le q_2 \le n$），表示第二位候选人的要求数量。 接下来 $q_2$ 行，每行包含两个整数 $k$ 和 $x$（$1 \le k \le n$，$1 \le x \le n$），表示城市编号和在其子树内需要建设的港口数量。 保证给定的边能够构成有效的树，每位候选人对每个城市的要求最多只提出一次，并且每位候选人都对自己选择的首都提出了港口建设要求。也就是说，城市 $x$ 一定在第一位候选人的要求中，城市 $y$ 一定在第二位候选人的要求中。

输出一个整数，表示在满足两位候选人所有要求的前提下，最多可以获得的收益。如果无法满足所有要求，则输出 $-1$。

在第一个样例中，最优方案是在城市 $2$、$3$ 和 $4$ 建设港口，满足了两位候选人的所有要求，收益为 $2 + 3 + 4 = 9$。 在第二个样例中，最优方案是在城市 $2$ 和 $3$ 建设港口，满足了两位候选人的所有要求，收益为 $99 + 99 = 198$。 在第三个样例中，无法在满足两位候选人所有要求的前提下建设港口，因此答案为 $-1$。 由 ChatGPT 4.1 翻译