Codeforces Round 523 (Div. 2) |
---|
Закончено |
В стране есть $$$n$$$ городов.
Два кандидата борются за пост президента страны. Выборы состоятся в скором будущем и оба кандидата уже спланировали как они собираются соединить города дорогами. Каждый из планов соединяет города используя ровно $$$n - 1$$$ дорогу. Иначе говоря, каждый план представляет из себя дерево. Оба кандидата также выбрали предлагаемую столицу среди $$$n$$$ городов ($$$x$$$ у первого кандидата, и $$$y$$$ у второго), которая может как совпадать, так и нет.
В каждом городе можно построить порт (в одном городе можно построить не более одного порта). Порт, построенный в $$$i$$$-м городе принесёт $$$a_i$$$ денег. Однако, у каждого кандидата есть свои специфичные требования, выглядящие следующим образом:
Выясните, какую наибольшую выручку можно получить, удовлетворив требованиям обоих кандидатов, или выведите -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, если это сделать невозможно.
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
9
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
198
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
-1
В первом примере оптимально построить порты в городах $$$2$$$, $$$3$$$ и $$$4$$$, что удовлетворяет всем требованиям обоих кандидатов и приносит прибыль $$$2 + 3 + 4 = 9$$$.
Во втором примере оптимально построить порты в городах $$$2$$$ и $$$3$$$, что удовлетворяет всем требованиям обоих кандидатов и приносит прибыль $$$99 + 99 = 198$$$.
В третьем примере не возможно построить порты таким образом, чтобы удовлетворить всем требованиям, а значит ответ -1.
Название |
---|