234
правки
Изменения
→Оценка времени работы
{{Лемма
|id = Lemma1
|statement= На пути от вершины до корня не больше <tex>log(n)</tex> легких ребер. |proof = Пусть <tex>m</tex> {{---}} количество вершин в дереве с корнем в вершине, в которой мы сейчас находимся. Поднимаясь по легкому ребру, <tex>m</tex> увеличивается в два раза, поэтому, пройдя больше <tex>\log (n)</tex> легких ребер, получим <tex>m > n</tex>. Значит, в дереве не больше <tex>\log (n)</tex> легких ребер. }}
Операция <tex>u</tex> осуществляется с помощью последовательности преобразований dashed-ребра в solid-ребро и другого solid-ребра в dashed-ребро. Обозначим количество таких преобразований за <tex>M</tex>. Найдем количество преобразований сделанных в течение <tex>expose(u)</tex>. Пусть <tex>H</tex> - множество всех тяжелых ребер, <tex>L</tex> - все легкие ребра, <tex>S \rightarrow D</tex> - множество solid-ребер, преобразованных в dashed в течение одного <tex>expose</tex>, <tex>D \rightarrow S</tex> - множество dashed-ребер, преобразованных в solid.
