Проблема HackerRank-city представляет собой построение ацикличного связного графа (дерева) в N этапов. Процесс создания дерева описан следующим образом: - Изначально имеется 1 узел. - На каждом шаге необходимо создать 3 дубликата текущего дерева и добавить 2 новых узла, соединяющих все 4 копии в форме буквы H. На каждом i-ом шаге дерево увеличивается в 4 раза, плюс добавляются 2 новых узла и 5 новых рёбер, соединяющих все части. Длина новых рёбер, добавляемых на шаге i, задается входным значением A. Необходимо вычислить сумму расстояний между каждой парой узлов; так как ответы могут быть большими, выведите результат по модулю 1000000007. **Формат ввода:** Первая строка содержит целое число N (количество шагов). Вторая строка содержит N разделённых пробелами целых числа, описывающих A, A1,…, AN-2, AN-1. **Примеры ввода:** Пример 0: 1 1 Вывод 0: 29 Пример 1: 2 2 1 Вывод 1: 2641 В дополнение, мне нужна помощь в понимании формулы 12X + 8. Как можно разъяснить эту формулу? Я застряла и не могу двигаться дальше. P.S. Изображения не загружаются.
В задаче HackerRank City описывается процесс создания дерева, и в формуле для подсчета расстояний между узлами действительно используется число 8. Давайте разберемся, откуда это число берется, и как оно связано с процессом построения дерева. 1. **Структура дерева**: - На начальном этапе у вас есть 1 узел. - На i-ом этапе вы создаете 3 дубликата текущего дерева и добавляете 2 новых узла, которые соединяют все 4 части дерева в форме буквы "H". Таким образом, на каждом шаге количество узлов увеличивается, и при добавлении новых рёбер увеличивается и длина расстояний между узлами. 2. **Учет расстояний**: - Когда вы добавляете новое ребро (длиной A), это влияет на расстояния между узлами разных частей дерева. Каждый добавленный узел и ребра создают новые пары узлов, между которыми нужно учитывать расстояния. 3. **Формула 12X + 8**: - Параметр X в данной формуле может быть связан с количеством узлов или рёбер на определенном этапе постройки дерева. Например, с каждым добавлением нового уровня количество узлов и рёбер изменяется, что влияет на итоговые расстояния. - Константа 8 может отражать некий фиксированный прирост расстояний, который не зависит от A или других переменных и всегда учитывается при подсчете суммы расстояний. ### Пояснение чисел: - **12X** может означать, что при увеличении дерева на 4 узла количество пар (которые теперь придется учитывать) увеличивается в 12 раз. Это может происходить из-за того, что каждая новая пара узлов из 4 новых узлов образует несколько новых расстояний. - **+ 8** — это фиксированный вклад, который добавляется в каждом этапе (например, количество новых рёбер, создаваемое при каждом добавлении новых узлов), и который не изменяется от шага к шагу. Чтобы точно понять, почему именно 8, вам нужно будет проанализировать, какие расстояния добавляются с каждым новым шагом, и как это влияет на общую сумму расстояний между узлами. Обычно это делается через комбинаторный анализ пар узлов и структуру самого дерева. Таким образом, чтобы разобраться в формуле, вам стоит внимательно анализировать процесс добавления новых узлов и рэбер, а также фиксированный вклад, который они могут давать на каждом этапе.
Это формула просто уже причесана и разложенна на множители. Это 12Y+8 (не X, кстати) идет в слагаемом (12Y+8)*(X+Y*Ai)
8 там - это 4*2. 4 дерева и 2 новые вершины. Подробнее ниже.
Как подсчитать все расстояния? Давайте отдельно посмотрим на те, которые внутри копии из 4 деревьев. Это даст нам слагаемое 4*Answer . Теперь подсчитаем те, которые идут между двумя разными деревьями. Их можно рзабить на 2 части - куски среди 5 новых ребер длины Ai и куски внутри деревьев. Вот эти куски внутри деревьев они все будут из угла, которым дерево крепится к остальным. Поэтому нам надо считать вот эту вот сумму расстояний от угла дерева (X).
Новые ребра посчитаем отдельно. В скольки путях каждое ребро будет присутствовать? Это надо перемножить количество вершин с одного конца ребра на количество вершин с другого конца. Ведь из каждой из первых есть путь во вторые, проходящий через данное ребро. Для 4-ех новых ребер размеры кусков будут Y и 3Y+2. Вот мы получили 4*Y*(3Y+2)*Ai . Вот тут если 4 внести внутрь мы получим вот это самое 12Y+8 из вопроса. Для одного ребра размеры будут 2Y+1 и 2Y+1. Вот мы получили слагаемое (2Y+1)^2*Ai .
Дальше надо посчитать, сколько раз каждый кусок в дереве из угла пойдет в ответ из путей между деревьями. Опять же, ровно столько раз, сколько вершин можно взять в качестве другого конца. Таких веришин 3*Y+2 - в любом из трех остальных деревьях или 2 новые вершины. Но эти куски в каждом из 4 деревьев, поэтому надо домножить на 4. Это дает нам слагаемое 4*X*(3Y+2) . Тут тоже вылезает 12Y+8.
Вот и получается формула там.
Чтобы пересчитать Y, понятно что надо умножить на 4 и прибавить 2. 4 дерева 2 новые вершины.
Вот с X по сложнее. Во-первых. там могут быть пути внутри одного дерева. Получаем слагаемое X . Во-вторых, надо посчитать, сколько раз каждое из новых ребер войдет в ответ. Ребро у дерева с углом с одной стороны имеет ровно одну вершину конец - угол. С другой может быть в любом дереве или в одной из 2 новых вершин. Поэтому получаем слагаемое (3Y+2)*Ai Ребро между новыми вершинами с одной стороны может кончатся в любом из 2 деревьев или в новой вершине. Получаем (2Y+1)*Ai . Оставшиеся 3 ребра ведут только в одно дерево и дают 3*Y*Ai .
Куски путей внутри других деревьев однозначно описываются одной вершиной концом и дают как раз все возможные пути из корня, т.е. получаем еще 3X .
Куски путей внутри корневого дерева - это всегда диаметр дерева Z который идет рвоно столько раз, сколько там других вершин в дереве (3Y+2). Получаем Z*(3Y+2) .
Если все сложить и причесать, получим ответ в статье. Возможно там чуть другая логика вывода была, но суть решения такая же. Аккуратно считаем все пути. Чтобы это было проще все пути можно разбить на группы: внутри дерева, между двумя разными, и еще и на части: часть в дереве и часть в новой серединке. И главный инструмент: ребро встречается в сумме путей ровно столько раз, сколько путей через него проходит, а это произведение размеров подграфов с двух концов ребра.