24
правки
Изменения
м
Правка пунктуации
===Препроцессинг===
Препроцессинг заключается в том, чтобы посчитать функцию: <tex> dp[v][i] </tex> {{---}} номер вершины, в которую мы придём если пройдём из вершины <tex> v </tex> вверх по подвешенному дереву <tex> 2 ^ i </tex> шагов, причём если мы пришли в корень, то мы там и останемся.
Для этого сначала обойдем дерево в глубину , и для каждой вершины запишем номер её родителя <tex> p[v] </tex> и глубину вершины в подвешенном дереве <tex> d[v] </tex>. Если <tex> v </tex> {{---}} корень, то <tex> p[v] = v </tex>. Тогда для функции <tex> dp </tex> есть рекуррентная формула:
<tex>dp[v][i]= \begin{cases}
