Пусть нам очень хочется решить следующую задачку:

Дано дерево и поступают два вида запросов — добавить X на пути, посчитать минимум вне пути. И требуется отвечать на каждый запрос за $$$O(n \cdot log^2n)$$$

Решение курильщика: Давайте сделаем HLD декомпозицию, и для каждого пути будет также хранить его id и минимум в нем. И будем хранить эти величины в множестве. Тогда запрос на добавление на пути — просто делаем стандартное обновление на пути в HLD, изменяя значения в множестве. Запрос минимума уже более интеллектуальный, посмотрим, на какие пути он разбивается, и выкинем их из множества (если путь входит частично, то мы только конец пути будем учитывать в ответе, и также будем выкидывать путь из множества). А ответ — минимум из этой величины и минимума в множестве. Так как все пути в множестве нам подходят. А ничего лишнего мы также не учли. Затем все откатываем и радуемся жизни.

Нормальное решение: Давайте просто сделаем HLD Вадомара (то бишь HLD, у которого можно спрашивать про поддеревья). И запрос изменения — обычный update в HLD, а чтобы получить ответ просто присвоим бесконечность на пути, и возьмем минимум.

Скорее всего многие это знали, но как по мне все равно забавно.