97
правок
Изменения
м
→Препроцессинг
\end{cases}</tex>
Для того чтобы отвечать на запросы нам нужны будут только те значения <tex> dp[v][i] </tex>, где <tex> i \le leqslant \log_2{n} </tex>, ведь при больших <tex> i </tex> значение <tex> dp[v][i] </tex> будет номером корня.
Всего состояний динамики <tex> O(n \log{n})</tex>, где <tex> n </tex> {{---}} это количество вершин в дереве. Каждое состояние считается за <tex> O(1) </tex>. Поэтому суммарная сложность времени и памяти препроцессинга {{---}} <tex> O(n \log{n}) </tex>.
