Задача к ЕГЭ по информатике на тему «графы» №1

Вам дан граф — бинарное дерево, то есть у каждой вершины есть не более двух детей, то есть не более двух исходящих ориентированных рёбер. Также никакая вершина не может быть ребёнком сразу двух вершин, иными словами для каждой вершины существует не более одного ориентированного ребра ведущего в эту вершину. В данной задаче в каждой вершине, у которой есть хотя бы один ребёнок, записана сумма величин записанных во всех детях. Вы можете изменить число ровно в одной вершине, причем изменять числа вы можете лишь в тех вершинах, у которых нет детей. Также вы не можете записывать в вершинах величины превышающие $100$ .

После того, как вы измените число, все числа во всех вершинах, которые содержат детей будут перечитаны по описанному выше правилу. Найдите максимальную сумму чисел записанных во всех вершинах.

Заметим, что при изменении числа $x$ на $y$ , в вершине на высоте $h$ , к сумме всех чисел на всех вершинах прибавляется $(y− x) ⋅h$ . Далее задача тривиальна, достаточно перебрать все висячие вершины (листы) и подсчитать $(100− x)⋅h$ , где $x$ — число записанное в вершине, а $h$ — высота (то есть количество ребер до корня $+ 1$ ) вершины.

Можно немного оптимизировать подсчёт ответа: давайте для каждого уровня (глубины, то есть удаленности от корня) считать ответ только для листа, в котором написано наименьшее число.

Также стоит заметить, что изначальную сумму удобнее всего посчитать как сумму произведений чисел, которые записаны в листах, на глубину листов.

В конкретном примере сумма чисел на всех вершинах изначально: $2643$ . Лист с наименьшим значением на глубине $7 : 64$ и может принести $36 ⋅7 = 252$ , на глубине $6 : 46$ , может принести $54 ⋅6 = 324$ , на глубине $5 : 51$ и может принести $51⋅5 = 255$ , на глубине $4 : 8$ и может принести $92 ⋅4 = 368$ . Итого максимальная сумма $2643+ 368 = 3011$ .

Задача может получить множество развитий. На самом деле лучше думать не про абстрактное бинарное дерево, а про дерево отрезков. Для определения дерева отрезков по большому счету достаточно лишь определить целевую функцию: что будем хранить в вершине. $tree[x]$ в предложенной задаче это лишь сумма на полуинтервале $[l,r)$ — где $[l,r)$ — полуинтервал за который отвечает конкретная вершина. Полуинтервал для всех висячих вершин это $[t,t+ 1)$ , а для всех вершин, у которых есть два ребёнка — это объединение двух полуинтервалов детей. Вершин же у которых есть только $1$ ребёнок в стандартном дереве отрезков нет. Далее везде стоит понимать понятия отрезок и полуинтервал как синонимы. Очевидно, что в случае, когда вас интересуют лишь целые точки $[l,r] = [l,r+ 1)$ . Можно изменить то, что хранится в вершинах. Классические варианты — мин/макс на отрезке, произведение на отрезке. Можно хранить даже не числа, а целые массивы, например в отсортированном виде (для лучшего понимания можно изучить $MergeSort Tree$ ). Можно изменять целевую функцию. В предложенной задаче таковой является сумма величин во всех вершинах. Можно сделать целевой функцией значение в корне. Либо в какой-то вершине, тогда задача сведется к меньшему дереву отрезков, в котором выбранная вершина является корнем. Можно отступить от простых объектов и начинать хранить в вершине сразу несколько величин. Классическое применение для нахождения полуинтервала с максимальной суммой: хранить префикс и суффикс с максимальной суммой а также максимальную сумму на полуинтервале.

Ответ: 3011