1632
правки
Изменения
м
<code>
</code>
rollbackEdits.php mass rollback
===Препроцессинг===
Препроцессинг заключается в том, чтобы посчитать функцию: <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}
==Псевдокод==
'''function''' preprocess():
'''int[]''' p = dfs(0)
swap(v, u)
'''for''' i = log(n) '''downto''' 0
'''if''' d[dp[u][i]] - d[v] <tex>\geqslant 2 ^ i </tex>= 0
u = dp[u][i]
'''if''' v == u
u = dp[u][i]
'''return''' p[v]
==См. также==
