Не так давно Лёня и Лёша заняли первое место на Reversed VK Cup, и администрация…
- User
Не так давно Лёня и Лёша заняли первое место на Reversed VK Cup, и администрация предлагает им выбрать себе подарки. Подарки лежат в коробочках, и каждая коробочка подвешена за некоторую другую; приз с номером 1 подвешен к потолку актового зала, в котором происходит награждение. Для каждого подарка известна его ценность для ребят — некоторое число. Иными словами, подарки и верёвочки образуют дерево со взвешенными вершинами с корнем в вершине под номером 1.
Каждый из ребят выбирает себе подарок отдельно. После того, как участник выбрал подарок, он вырезает его из структуры, и всё поддерево подарка падает на пол; соответственно, из этого поддерева больше нельзя выбрать подарок. Лёня и Лёша хотят выбрать себе по одному подарку так, чтобы их суммарная ценность была максимальной, а взять эти подарки вместе было возможно. Другими словами, им требуется выбрать две различные вершины дерева с максимальной суммой весов так, чтобы ни одна из этой пары не являлась предком другой.
Помогите ребятам, и, может быть, вы тоже когда-нибудь сможете занять первое место на Reversed VK Cup.
В первой строке входного файла дано число n — количество подарков (1 ≤ n ≤ 105).
Во второй строке входного файла даны n целых чисел, i-e число определяет ценность подарка с номером i (ценность подарка неотрицательна и не превосходит 109).
В следующих n - 1 строках даны пары чисел v, w — номера подарков, связанных верёвочкой. Подарки нумеруются с 1.
Формат файла выходных данных:
В единственной строке выходного файла выведите число k — максимально возможную суммарную ценность подарков ребят. Если выбрать подарки требуемым образом невозможно, выведите -1.
Пример: 3 2 1 5 2 1 3 1
6
- Assistant
Для решения данной задачи мы можем использовать подход, основанный на обходе дерева. Основная идея заключается в том, чтобы найти две вершины, которые не имеют родительско-потомковых отношений, и максимизировать их суммарную ценность.
Рассмотрим шаги решения:
-
Чтение входных данных: Нам необходимо получить количество подарков, их ценности и связи между ними в виде графа (в данном случае - дерева).
-
Построение дерева: Мы будем использовать список смежности, чтобы представить дерево, где каждая вершина (подарок) связана с другими.
-
Поиск двух наибольших ценностей в разных поддеревьях: Для каждого узла в дереве мы будем искать максимальные ценности подарков среди его детей. Сохраним информацию о наибольшем и втором по величине значении для каждого узла.
-
Подсчет суммарной ценности: Для каждого узла дерева, если он имеет как минимум два различных потомка с наибольшими весами, мы можем комбинировать их ценности, чтобы получить кандидата для ответа.
-
Вывод результата: После перебора всех узлов мы сможем решением, состоящим в выводе максимального значения, либо -1, если такие пары не были найдены.
Ниже приведен реализованный код для данного алгоритма на Python:
def find_max_pair_value(n, values, edges): from collections import defaultdict # Построим граф дерева tree = defaultdict(list) for v, w in edges: tree[v].append(w) tree[w].append(v) # Храним максимальные и второстепенные значения max_values = [0] * (n + 1) second_max_values = [0] * (n + 1) visited = [False] * (n + 1) def dfs(node): visited[node] = True first_max = 0 second_max = 0 for neighbor in tree[node]: if not visited[neighbor]: dfs(neighbor) # Выбираем максимальные и вторые максимальные значений if max_values[neighbor] > first_max: second_max = first_max first_max = max_values[neighbor] elif max_values[neighbor] > second_max: second_max = max_values[neighbor] max_values[node] = first_max second_max_values[node] = second_max # Начинаем обход с корневого узла (узел 1) dfs(1) # Находим максимальную сумму двух разных подарков maximum_sum = -1 for i in range(1, n + 1): if max_values[i] > 0 and second_max_values[i] > 0: maximum_sum = max(maximum_sum, max_values[i] + second_max_values[i]) return maximum_sum # Чтение входных данных n = int(input()) values = list(map(int, input().split())) edges = [tuple(map(int, input().split())) for _ in range(n - 1)] # Прямую ценность накапливаем в values for i in range(1, n + 1): values[i - 1] = (values[i - 1], i) # Решение result = find_max_pair_value(n, values, edges) print(result)Примечания
- Код обрабатывает дерево с помощью DFS (поиск в глубину).
- Мы сохраняем максимум и второе по величине значение в каждом узле, чтобы в дальнейшем легко комбинировать их для получения максимальной суммы.
- Обработка начинается с корневого узла, что в данном случае соответствует узлу с номером 1.
-