Редактирование: Link-Cut Tree

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 114: Строка 114:
 
}}
 
}}
  
Операция <tex>u</tex> осуществляется с помощью последовательности преобразований пунктирного ребра в сплошное ребро и другого сплошного ребра в пунктирное ребро. Обозначим количество таких преобразований за <tex>M</tex>. Найдем количество преобразований сделанных в течение <tex>\mathrm{expose(u)}</tex>. Пусть <tex>H</tex> {{---}} множество всех тяжелых ребер, <tex>L</tex> {{---}} все легкие ребра, <tex>S \rightarrow D</tex> {{---}} множество сплошных ребер, преобразованных в пунктирные в течение одного <tex>\mathrm{expose}</tex>, <tex>D \rightarrow S</tex> {{---}} множество пунктирных ребер, преобразованных в сплошные.
+
Операция <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.
  
 
<tex>M = |\{D \rightarrow S\}| = |\{L \cap D \rightarrow S\}| + |\{H \cap D \rightarrow S\}|</tex>
 
<tex>M = |\{D \rightarrow S\}| = |\{L \cap D \rightarrow S\}| + |\{H \cap D \rightarrow S\}|</tex>
  
По лемме, количество легких пунктирных ребер, преобразованных в сплошные, будет не больше, чем <tex>\log n</tex>.
+
По лемме, количество легких dashed-ребер, преобразованных в solid, будет не больше, чем <tex>\log n</tex>.
  
Обозначим за <tex>F</tex> лес деревьев, в которых каждое ребро либо сплошное, либо пунктирное, 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>.
+
Обозначим за <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>.
  
 
{{Лемма
 
{{Лемма

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: