Не так давно Лёня и Лёша заняли первое место на Reversed VK Cup, и администрация…
- User
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. User: напиши на голанг Assistant:
-
- Assistant
Конечно! Вот реализация алгоритма на языке Go для решения задачи по выбору подарков из дерева. Мы будем использовать DFS для обхода дерева и поиска двух максимальных значений подарков в поддеревьях.
package main import ( "fmt" ) type TreeNode struct { value int children []*TreeNode } func dfs(node *TreeNode, maxValues *[]int, secondMaxValues *[]int) { firstMax, secondMax := 0, 0 for _, child := range node.children { dfs(child, maxValues, secondMaxValues) if (*maxValues)[child.value] > firstMax { secondMax = firstMax firstMax = (*maxValues)[child.value] } else if (*maxValues)[child.value] > secondMax { secondMax = (*maxValues)[child.value] } } (*maxValues)[node.value] = firstMax (*secondMaxValues)[node.value] = secondMax } func main() { var n int fmt.Scan(&n) values := make([]int, n+1) for i := 1; i <= n; i++ { fmt.Scan(&values[i]) } tree := make([]*TreeNode, n+1) for i := range tree { tree[i] = &TreeNode{value: i, children: []*TreeNode{}} } for i := 0; i < n-1; i++ { var v, w int fmt.Scan(&v, &w) tree[v].children = append(tree[v].children, tree[w]) tree[w].children = append(tree[w].children, tree[v]) // так как дерево неориентированное } // Для использования DFS храним максимальные значения maxValues := make([]int, n+1) secondMaxValues := make([]int, n+1) // Начинаем обход с корневого узла (узел 1) dfs(tree[1], &maxValues, &secondMaxValues) // Находим максимальную сумму двух разных подарков maximumSum := -1 for i := 1; i <= n; i++ { if maxValues[i] > 0 && secondMaxValues[i] > 0 { maximumSum = max(maximumSum, maxValues[i]+secondMaxValues[i]) } } fmt.Println(maximumSum) } func max(a, b int) int { if a > b { return a } return b }Объяснение кода:
- Структура TreeNode: Представляет узлы дерева, каждый узел хранит свое значение и список детей.
- DFS функция: Находит максимальные и второстепенные максимальные значения в поддеревьях.
- Основная функция:
- Читает количество узлов и их значения.
- Строит неориентированное дерево.
- Запускает DFS с корневым узлом.
- Находит максимальную сумму двух подарков, которые могут быть выбраны.
- Функция
max: Определяет максимальное значение между двумя целыми числами.
Запуск программы:
- Скомпилируйте код с помощью
go buildи запустите его. - Введите количество подарков и их ценности, а затем связи между ними в виде пар чисел.
Программа выведет максимальную возможную суммарную ценность подарков, которые могут выбрать Лёня и Лёша. Если такого выбрать нельзя, будет выведено -1.