← 返回题目列表

Codeforces · 1061/E

E. 政治

中文机器翻译题面 查看原题

该国有 $$$n$$$ 个城市。

两名候选人正在争夺总统职位。选举已定在未来,两位候选人都已经计划好了如何将城市与道路连接起来。这两个计划都将仅使用 $$$n - 1$$$ 道路连接所有城市。也就是说,每个计划都可以被视为一棵树。两位候选人还指定了他们在 $$$n$$$ 城市中选择的首都(第一位候选人为 $$$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。

示例

输入 #1

4 1 2
1 2 3 4
1 2
1 3
3 4
1 2
2 3
1 4
2
1 3
4 1
1
2 3

输出 #1

9

输入 #2

5 1 1
3 99 99 100 2
1 2
1 3
3 4
3 5
1 3
1 2
2 4
2 5
2
1 2
3 1
2
1 2
2 1

输出 #2

198

输入 #3

4 1 2
1 2 3 4
1 2
1 3
3 4
2 1
2 4
4 3
1
1 4
2
4 1
2 4

输出 #3

-1

注意

在第一个示例中,最佳方案是在 $$$2$$$、$$$3$$$ 和 $$$4$$$ 城市建设港口,这满足了两个候选人的所有需求,并提供等于 $$$2 + 3 + 4 = 9$$$ 的收入。

在第二个示例中,最佳方案是在 $$$2$$$ 和 $$$3$$$ 城市建设港口,这满足了两个候选人的所有需求,并提供等于 $$$99 + 99 = 198$$$ 的收入。

在第三个示例中,不可能以指定两个候选者的所有需求的方式构建端口,因此答案为-1。