AB
Ну и да, нужно как строку обрабатывать, как уже подметили
Size: a a a
2021 May 24
AD
Понял принял
AD
Спасибо
2021 May 25
f
Как с помощью центроидной декомпозиции отвечать на дереве на запросы поменять вес вершины, найти путь максимального веса проходящий через нее?
K
А точно тут она нужна?
f
не точно, это лишь мое предположение
f
Готов рассмотреть другие варианты))
f
Но вроде бы ею можно решить эту задачу
EZ
Можно с хлд вроде, просто для каждого блока хранить вес и максимум из путей вниз, обновляется за логарифм и считается за логарифм
EZ
Но я не настоящий сварщик
K
Вроде да.
Смотрите. Делаем структуру, решающую запросы (изменить вес вершины) и (найти самый тяжелый путь, проходящий через вершину и корень). Первый раз корнем делаем центроид, потом так же для декомпоз-деревьев
Смотрите. Делаем структуру, решающую запросы (изменить вес вершины) и (найти самый тяжелый путь, проходящий через вершину и корень). Первый раз корнем делаем центроид, потом так же для декомпоз-деревьев
K
И для каждой вершины храним список структур, в которых она есть
K
Структура на базе дерева отрезков
K
А как учитывать пути (вверх, а потом вниз)?
K
Где такую красоту нашли?
EZ
Ну максимальный вес это максимум по блокам-родителям путей проходящих через них
EZ
Там правда детей надо проверять
EZ
А это наверное асимптотику ломает
K
Вроде то, что я сказал, каждый запрос за log^2
K
Откуда такая красота, поделитесь?