5. Lucky Tree (Div1 C, Div2 E)

Решим задачу используя метод динамического программирования. Подвесим дерево за какую-то вершину, например 1. Пусть F(x) - количество вершин в поддереве x таких, что на пути из x в эту вершину есть как минимум одно счастливое ребро. Считать F(x) будем рекурсивно. Если x - листок дерева, то F(x) = 0. Иначе, если от x выходит счастливое ребро в y, то к F(x) нужно додать C(y), иначе F(y) (Здесь C(x) - количество вершин в поддереве x, включая вершину x). Но для решения этой задачи, нам нужно еще знать для каждой вершини количество вершин вне поддерева, на пути до которых есть счастливое ребро. Назовем это количество F'(x). Для корня дерева F' ровно 0. Будем идти рекурсивно из вершины-корня, при этом если мы рассматриваем какую-то вершину, то F' для нее уже посчитан. Пусть сейчас мы в вершине x и хотим перейти в вершину y. Если ребро между этими вершинами счастливое, то F'(y) = C(0) - C(y), иначе F'(y) = F'(x) + F(v) - F(to) (действительно, если ребро не счастливое, то нам к результату для x нужно еще додать сумму F(i) для всех i которые есть синовями x и i ≠ y).

После этого результатом будет

При ограничениях a и b до 10⁷ задача решается используя КМП: рассмотрим строку следуещего вида: F(1)F(2)F(3)F(4)...F(3 * 10⁷). Нужно найти первое вхождение после индекса a строки F(a)F(a + 1)F(a + 2)...F(a + l - 1). Сложность такого решения O(a + l), естественно что такое не проходит по времени и памяти. Попробуем оптимизировать этот алгоритм используя несколько фактов из "Теории счастливых чисел".

Разобьем все числа на блоки по 100, то есть первый блок - [0;99], второй - [100;199] и т. д. Введем понятие класса блока. Номер класса блока ровен F(i / 100), где i - какое-то число из этого блока. Различных классов блоков будет ровно 8. Подряд-идущих блоков с одинаковыми номерами классов будет максимум 6. Все это можно увидет используя перебор. 

Утверждение #1: если l ≥ 1000, то .

Доказательство: рассмотрим строку F(100 * k)F(100 * k + 1)...F(100 * k + 99). Таких различных строк буде столько само, сколько различных классов. Например, для первого класса она будет иметь вид:

для второго:

и т.д. По структуре этих строк видно, что блоки различних классов не могут пересекаться (то есть при любом пересечениее освпадения не будет), отсюда следует, что любая последовательность подряд идущих блоков в которой есть хотя-бы два блоки с различными классами будет совпадать только с такой самой последовательностью, то есть смещение будет кратное 100. Так как подояд-идущих блоков с одинаковимы классами будет не больше 6, то при l ≥ 1000, очевидно, будут различные блоки, что и требовалось доказать.

Поэтому, задачу с l ≥ 1000 можно решить используя алгоритм КМП со сложностью O((a + l) / C), где C равно 100, пусть функция которая будет это делать называется Solve(l, r).

Тепер нужно научиться решать задачу с l < 1000. Сначала заменим a на минимальное a' такое, что F(a') = F(a), F(a' + 1) = F(a + 1), ..., F(a' + l - 1) = F(a + l - 1), a' / 100 = a / 100, это можно сделать простым перебором. Тогда результат будет минимум из следующих чисел:

- r = Solve(a', a' + l - 1);

- Минимального r', такого что r - r' <  = 1000, r' > a, F(r') = F(a), F(r' + 1) = F(a + 1), ..., F(r' + l - 1) = F(a + l - 1).

- Минимального a'' такого, что a'' > a, a'' - a ≤ 1000 и F(a'') = F(a), F(a'' + 1) = F(a + 1), ..., F(a'' + l - 1) = F(a + l - 1).

Естественно это решает проблему возможного не кратного 100 смещения блоков, но есть и вариант, который ставит это под сомнение. Пусть входной промежуток только в блоке с номером класса C. Тогда, есть вероятность, что лучше пойти в блок с номером C + 1, например (397;1) → (400;1). На самом деле, второй пункт решает эту проблему, так как если и блок C + 1 будет перед блоком C (а только в том случаи будет выгоднее его взять), то эти два блоки будут соседними (здесь имеется ввиду блок с классом C, правее блока со входным промежутком). Доказать это можно следующим, довольно важным, утверджением (с помощью которого можна доказывать и другие моменты), подтвердить которое можно перебором:

Утверждение #2: если есть два соседних блока, то абсолютная разница номеров их классов не превысшает 1.

Отсюда следует, что если после блока C (в котором есть входной промежуток) идет блок C - 1, то до блока C мы доберемся перед C + 1, если до C или C + 1 то его и выберем.

Таким образом, задача решается просто аккуратным разбором всех моментов. Сложность решения: O((A + L) / 100), авторское решние работает 1.5 сек. и использует 250 мб. памяти.