Боб начинает свой путь в Тинькофф Инвестициях. Сейчас его интересуют k компаний, и он обязательно хочет купить акции всех этих компаний, чтобы у каждой компании была хотя бы одна акция. Тинькофф Инвестиции предложили ему корневое дерево из n вершин, в каждой из которых лежит пакет акций какой-то из интересующих его компаний, также задана стоимость каждого пакета. Вершины корневого дерева пронумерованы целыми числами от 1 до n. Функционал нынешнего приложения позволяет Бобу купить поддерев

Шаги решения задачи:

1. Создадим два списка: один для хранения стоимостей пакетов акций (cost), и другой – для хранения информации о наличии пакета акций в каждой вершине (exists). Оба списка будут иметь длину n, где n – количество вершин в дереве.

2. Заполним список exists значениями False для всех вершин.

3. В цикле пройдемся по всем интересующим Боба компаниям и установим значение True для вершин, в которых находятся пакеты акций этих компаний.

4. Используя алгоритм обхода дерева в глубину, начиная с корневой вершины, проверим наличие комплекта акций в поддереве каждой вершины.

5. Если в поддереве вершины есть все интересующие Боба компании и в вершине не находится пакет акций этих компаний, то устанавливаем значение exists вершины в True.

6. Продолжаем рекурсивный обход дерева, перемещаясь от родительских вершин к дочерним.

7. По окончании обхода дерева, осуществляем проверку, есть ли комплект акций в корневой вершине и возвращаем соответствующий результат.

Пример кода на Python:

“`
def check_stocks(root, exists, cost):
# устанавливаем значения exists для интересующих Боба компаний
for i in range(len(root)):
if root[i] == True:
exists[i] = True

# рекурсивная функция для обхода дерева
def traverse(node):
stocks_available = True

# проверяем наличие всех интересующих компаний в поддереве вершины
for i in range(len(cost)):
if exists[i] == False and node[i] == True:
stocks_available = False
break

# устанавливаем значение exists для вершины, если доступны все интересующие компании
if stocks_available:
exists[node.index(True)] = True

# рекурсивный обход дерева
for i in range(len(node)):
if node[i] == True:
traverse(root[i])

# вызываем функцию обхода для корневого элемента
traverse(root[0])

# проверяем наличие комплекта акций в корневой вершине
stocks_complete = True
for i in range(len(cost)):
if exists[i] == False:
stocks_complete = False
break

return stocks_complete
“`

Временная сложность этого алгоритма зависит от количества вершин в дереве и равна O(n), где n – количество вершин в дереве.