Обсуждение @ 1471. Расстояние в дереве @ Timus Online Judge

Online Judge	Задачи	Авторы	Соревнования
О системе Часто задаваемые вопросы Новости сайта Форум Ссылки	Архив задач Отправить на проверку Состояние проверки Руководство	Регистрация Исправить данные Рейтинг авторов	Текущее соревнование Расписание Прошедшие соревнования Правила

Обсуждение задачи 1471. Расстояние в дереве

sak3t AC in 0.249 and 8668 KB (RMQ for lca) [1] // Задача 1471. Расстояние в дереве 29 май 2017 15:39

used RMQ using segment tree to find lca in log(n)
total time complexity O(n+q*(lgn)) = O(q*lgn)

Mahilewets Re: AC in 0.249 and 8668 KB (RMQ for lca) // Задача 1471. Расстояние в дереве 15 июн 2017 22:06

Almost the same numbers (0.268, 11500) for table for 2^i -th ancestor.