Тема: Дерево 2
Как можно решить эту задачу http://acm.timus.ru/problem.aspx?space=1&num=1752???
Пытался решить бинпоиском + LCA но WA. Как можно ее по другому решить?
спасибо
Re: Дерево 2
Может, просто найти диаметр дерева, и затем искать ответ в виде "дойти от v_i до диаметра, дальше идти вдоль него" ?
Re: Дерево 2
При этом сложность какой будет?
Там Q запросов, а каждый запрос за O(N). Значит в общей сложности O(QN) Q=5*10^4, N = 2*10^4 => 10^9 операций вроде выходит.
Re: Дерево 2
Да не, если идея правильная, то можно и за logN отвечать на запрос - двоичным подъёмом дойти до диаметра, а оказавшись в диаметре, уже просто взять k-ый элемент этого диаметра (диаметр сохранить заранее в отдельном списке).
5 2011-08-25 01:21:26 Отредактировано KADR (2011-08-25 01:22:46)
Re: Дерево 2
Да там просто от каждой вершины надо самую дальнюю найти и запомнить, как мы туда шли: сразу вниз или вверх до куда-то, а потом вниз. Делается двумя дфсами.
Ну а после этого можно либо двоичным подъемом на все запросы в онлайне отвечать, либо еще одним дфсом в оффлайне за линию.