Изменения

Операция <tex>u</tex> осуществляется с помощью последовательности преобразований dashed-пунктирного ребра в solid-сплошное ребро и другого solid-сплошного ребра в dashed-пунктирное ребро. Обозначим количество таких преобразований за <tex>M</tex>. Найдем количество преобразований сделанных в течение <tex>\mathrm{expose(u)}</tex>. Пусть <tex>H</tex> {{---}} множество всех тяжелых ребер, <tex>L</tex> {{---}} все легкие ребра, <tex>S \rightarrow D</tex> {{---}} множество solid-сплошных ребер, преобразованных в dashed пунктирные в течение одного <tex>\mathrm{expose}</tex>, <tex>D \rightarrow S</tex> {{---}} множество dashed-пунктирных ребер, преобразованных в solidсплошные.

По лемме, количество легких dashed-пунктирных ребер, преобразованных в solidсплошные, будет не больше, чем <tex>\log n</tex>.

Обозначим за <tex>F</tex> лес деревьев, в которых каждое ребро либо solidсплошное, либо dashedпунктирное, a <tex>F'</tex> {{---}} лес, получившийся из <tex>F</tex> после одного вызова <tex>\mathrm{expose}</tex>. Определим потенциал <tex>\Phi _{a}(F) = n - 1 - |\{H \cap solid-edges\}|</tex>, <tex>\Delta \Phi _{a}</tex> {{---}} увеличение <tex>\Phi _{a}</tex> после одной операции <tex>\mathrm{expose}</tex>.