@ManyGames

Здравствуйте. У меня имеется рекурсивный метод:
На acmp решение с применением этого метода получет ML, думаю, что чтоб избежать этого, нужно избавиться от рекурсии.
Как это сделать для данного метода? У меня не очень-то получается

0

@xoraxax

На acmp решение с применением этого метода получет ML,
Чо?

0

@Aviz__

чего решаешь то? что есть свое решение - это хорошо, но условие всей задачи приведи.

0

@ManyGames

acmp - сайт с задачками
ML - Memory Limit Exceeded, превышение ограничений по памяти

Добавлено через 3 минуты
Вот задача на acmp:


И вот моё решение:
На codeforces такое решение прошло полностью, ибо там лимит по памяти 512 МБ

Добавлено через 4 минуты
Тут

0

@Aviz__

тебе нужна помощь, а мы должны ходить по ссылке!? Приведи текст задачи здесь.

0

@ManyGames

Пробовал избавиться от рекурсии при помощи очереди вот так:
Но все равно ML

Добавлено через 2 минуты
В лаборатории теоретической пиротехники изучают новые технологии организации фейерверков. Фейерверк представляется как корневое дерево, а поскольку в мощном фейерверке его элементы также взрываются, порождая новые фейерверки, то ученые вводят операцию возведения корневого дерева в степень.

Корневое дерево содержит одну или несколько вершин. Одна из вершин выделена и называется корнем дерева, для каждой из остальных вершин ровно одна другая вершина является родителем. При этом от любой вершины можно добраться до корня, последовательно переходя от вершины к ее родителю. Вершина, которая не является родителем никакой другой вершины, называется листом. Если вершина x является родителем вершины y, то вершина y является ребенком вершины x. Будем говорить, что вершина и ее родитель соединены ребром.
Фейерверк задается своим базовым деревом T и мощностью m. Фейерверк представляется деревом, которое получается в результате возведения дерева T в степень m. Операция возведения дерева в степень устроена следующим образом. Если m = 1, то результат T1 — само дерево T. Для m > 1 рассмотрим дерево Tm – 1. Выполним следующую операцию: для каждого листа x дерева Tm – 1 создадим копию дерева T и назначим лист x родителем корня соответствующей копии. Получившееся дерево будет деревом Tm.
Путем в дереве называется последовательность вершин, в которой две соседние вершины соединены ребром. Все вершины в пути должны быть различны.
Для того, чтобы оценить красоту фейерверка, необходимо определить, какое максимальное количество вершин может содержать путь в дереве, которым представляется фейерверк
Требуется написать программу, которая по описанию дерева T и натуральному числу m определяет красоту фейерверка с базовым деревом T и мощностью m.

Входные данные
Первая строка входного файла INPUT.TXT содержит два натуральных числа n и m – количество вершин в базовом дереве фейерверка T и его мощность (3 ≤ n ≤ 200 000, 1 ≤ m ≤ 200 000).
Вторая строка описывает дерево T и содержит (n – 1) целых чисел: p2, p3, …, pn – номера родителей вершин 2, 3, …, n, соответственно (1 ≤ pi ≤ i – 1).
Выходные данные
В выходной файл OUTPUT.TXT выведите одно целое число – красоту фейерверка, представляемого деревом Tm.

Пример:
Ввод:
4 2
1 1 2
Вывод:
10

0

@Aviz__

а базовое дерево с числом узлов 5, какой вид должно иметь?
вид 1:
-------1
-----2---3
----4
---5
или вид 2:
-------1
-----2---3
---4------5
Вид 2, в плане красоты, при умножении, на мой взгляд, лучше.
И почему нужно без рекурсии?
Если, скажем, любое дерево растет, по виду 1, то при умножении, все проще))

0

@ManyGames

Базовое дерево нельзя строить произвольно, зависит от входных данных. Например, входные данные такие
5 2
1 1 3 3
То базовое дерево выглядит так:
------1
---2----3
------4---5
Я решаю так: храню граф в списке смежности graph и выполняю поиск диаметра дерева.
Для данного примера список смежности выглядит так:
1) 2, 3
2) -
3) 4, 5
4) -
5) -
Но, для того чтоб выполнить второй обход в глубину, храню его как неориентированный граф.
Сначала запускаю первый dfs от первой вершины и ищу самую удаленную, в примере самая удаленная - 5. Запоминаю расстояние до неё в переменную z(3). Потом от самой удаленной вершины запускаю ещё раз dfs, в примере от пятой вершины самая удаленная - вторая, расстояние до неё - 4. А далее по формуле ans = max+(z*2)*(m-1) (где max - диаметр дерева, z - расстояние от первой вершины до самой удаленной, m - из условия) вывожу ответ. В примере z = 3, max = 4. ans = 4+(3*2)*(2-1) = 4+6 = 10

На codeforces, повторюсь, такое решение прошло, а на acmp нет - ML. Но на codeforces по памяти ограничение в 512 Мб, а на acmp - всего 16.

Добавлено через 4 минуты
То есть я рассматриваю только базовое дерево, а ответ высчитываю по формуле

0

@Aviz__

так чем тебе рекурсия не мила?

0

@ManyGames

Вероятно, стек при работе моего решения занимает много памяти, из-за этого решение не проходит
Но может я и ошибаюсь

0

@Aviz__

оптимизируй рекурсивный метод))

0

@ManyGames

Там, где 205 Мб - рекурсивный dfs, а там, где 36 Мб - без рекурсии (метод, который я писал выше).
Вы все ещё думаете, что рекурсивный метод можно оптимизировать?)

Миниатюры

 

0

@Aviz__

надеюсь, это поможет понять где у твоего рекурс метода засада https://www.cyberforum.ru/java/thread2250765.html - дебагер

0

@ManyGames

Засада?.. Алгоритм я вычитал в книге Антти Лааксонена "Олимпиадное программирование", им же и воспользовался. Не думаю, что спортивный программист такого высокого уровня может издать книгу, в которой некоторые алгоритмы "с засадами".

0

@Aviz__

ManyGames, Ок! Удачи)). Когда на авторитетов перестанешь кивать, продолжим...

1

@snickers0137

Твое решение неправильно работает. Контрпример:
4 2
1 2 3
Ответ:8, а у тебя 12.

1