Алгоритм Хьюи - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:35:59Z

rollbackEdits.php mass rollback

185.220.100.254 в 04:07, 1 сентября 2022

2022-09-01T04:07:52Z

78.25.120.113: /* Обоснование корректности */

2016-01-23T15:01:36Z

‎Обоснование корректности

Nikitaevg в 11:06, 17 января 2016

2016-01-17T11:06:46Z

Nikitaevg в 11:02, 17 января 2016

2016-01-17T11:02:48Z

Nikitaevg в 11:01, 17 января 2016

2016-01-17T11:01:00Z

Nikitaevg в 18:17, 16 января 2016

2016-01-16T18:17:34Z

Shersh: переименовал Алгоритм Хью в Алгоритм Хьюи: так вроде правильней

2016-01-02T10:34:26Z

переименовал Алгоритм Хью в Алгоритм Хьюи: так вроде правильней

Nikitaevg в 08:06, 2 января 2016

2016-01-02T08:06:18Z

Nikitaevg в 19:36, 30 декабря 2015

2015-12-30T19:36:37Z

← Предыдущая		Версия 16:35, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	{{Задача		{{Задача
	\|definition=Дано [[Основные определения теории графов#oriented_grath\|ориентированное]] [[Дерево, эквивалентные определения#tree\|дерево]], вершины которого раскрашены в цвета. Найти <tex>dc:V\rightarrow \{1\ldots k\}</tex>, где <tex>dc(u) -</tex> число различных цветов в поддереве с корнем в вершине <tex>u</tex>. Время работы: <tex>O(V)</tex>}}		\|definition=Дано [[Основные определения теории графов#oriented_grath\|ориентированное]] [[Дерево, эквивалентные определения#tree\|дерево]], вершины которого раскрашены в цвета. Найти <tex>dc:V\rightarrow \{1\ldots k\}</tex>, где <tex>dc(u) -</tex> число различных цветов в поддереве с корнем в вершине <tex>u</tex>. Время работы: <tex>O(V)</tex>}}

← Предыдущая		Версия 04:07, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	{{Задача		{{Задача
	\|definition=Дано [[Основные определения теории графов#oriented_grath\|ориентированное]] [[Дерево, эквивалентные определения#tree\|дерево]], вершины которого раскрашены в цвета. Найти <tex>dc:V\rightarrow \{1\ldots k\}</tex>, где <tex>dc(u) -</tex> число различных цветов в поддереве с корнем в вершине <tex>u</tex>. Время работы: <tex>O(V)</tex>}}		\|definition=Дано [[Основные определения теории графов#oriented_grath\|ориентированное]] [[Дерево, эквивалентные определения#tree\|дерево]], вершины которого раскрашены в цвета. Найти <tex>dc:V\rightarrow \{1\ldots k\}</tex>, где <tex>dc(u) -</tex> число различных цветов в поддереве с корнем в вершине <tex>u</tex>. Время работы: <tex>O(V)</tex>}}

@@ Строка 67: / Строка 67: @@
 ==Обоснование корректности==
-{{Лемма
+Отсортируем вершины по времени входа. Рассмотрим вершину <tex>v</tex>, в поддереве которой <tex>k</tex> вершин одного цвета. Так как мы обходим вершины в порядке времени входа, эти <tex>k</tex> вершин мы обойдем последовательно. Их наименьший общий предок будет лежать в данном поддереве. Следовательно мы вычтем <tex>k-1</tex> раз единицу из вершины <tex>v</tex>. Для любых других двух вершин их наименьший общий предок не будет лежать в данном поддереве. Следовательно для каждого поддерева учтется по одной вершине каждого цвета, существующего в данном поддереве.
 ==См. также==

@@ Строка 5: / Строка 5: @@
 ==Простое решение==
-Ответ на задачу можно получить достаточно просто с помощью битовых масок. Для начала в каждую вершину поместим битовую маску с цветом данной вершины. Запустим [[Обход в глубину, цвета вершин|обход в глубину]] и на выходе из каждой вершины будем записывать в неё результат побитового <tex>OR</tex> масок её детей и её самой. Таким образом в каждой вершине будет храниться битовая маска с цветами, лежащими в данном поддереве. Общая сложность алгоритма будет <tex>O(V \cdot K)</tex>, где <tex>K\ -</tex> количество цветов. Если количество цветов меньше размера машинного слова, то сложность будет <tex>O(V)</tex>.
+Ответ на задачу можно получить достаточно просто с помощью битовых масок. Для начала в каждую вершину поместим битовую маску с цветом данной вершины. Запустим [[Обход в глубину, цвета вершин|обход в глубину]] и на выходе из каждой вершины будем записывать в неё результат побитового <tex>OR</tex> масок её детей и её самой. Таким образом в каждой вершине будет храниться битовая маска с цветами, лежащими в данном поддереве. Общая сложность алгоритма будет <tex>O(V \cdot K)</tex>, где <tex>K\ -</tex> количество цветов. Если количество цветов меньше размера машинного слова, то сложность составит <tex>O(V)</tex>.
 ==Алгоритм решения==
@@ Строка 49: / Строка 49: @@
   '''func''' dfs('''Node''' v)''':'''
-     used[v] = <b>true</b>
+     used[v] = ''true''
      '''for''' <tex>u \in</tex> v.children
          '''if''' !used[u]
@@ Строка 60: / Строка 60: @@
   '''func''' hugh('''int''' n, '''int''' k, '''Node''' root)''':'''
      '''for''' <tex>v \in V</tex>
-         used[v] = <b>false</b>
+         used[v] = ''false''
          sum[v] = 1
-     '''for''' i = 1 to k
+     '''for''' i = 1 '''to''' k
          last[i] = -1
      dfs(root)

@@ Строка 5: / Строка 5: @@
 ==Простое решение==
-Ответ на задачу можно получить достаточно просто с помощью битовых масок. Для начала в каждую вершину поместим битовую маску с цветом данной вершины. Запустим [[Обход в глубину, цвета вершин|обход в глубину]] и на выходе из каждой вершины будем записывать в неё результат побитового <tex>OR</tex> масок её детей и её самой. Таким образом в каждой вершине будет храниться битовая маска с цветами, лежащими в данном поддереве. Общая сложность алгоритма будет <tex>O(V \cdot K)</tex>, где <tex>K</tex> - количество цветов. Если количество цветов меньше размера машинного слова, то сложность будет <tex>O(V)</tex>.
+Ответ на задачу можно получить достаточно просто с помощью битовых масок. Для начала в каждую вершину поместим битовую маску с цветом данной вершины. Запустим [[Обход в глубину, цвета вершин|обход в глубину]] и на выходе из каждой вершины будем записывать в неё результат побитового <tex>OR</tex> масок её детей и её самой. Таким образом в каждой вершине будет храниться битовая маска с цветами, лежащими в данном поддереве. Общая сложность алгоритма будет <tex>O(V \cdot K)</tex>, где <tex>K\ -</tex> количество цветов. Если количество цветов меньше размера машинного слова, то сложность будет <tex>O(V)</tex>.
 ==Алгоритм решения==

@@ Строка 1: / Строка 1: @@
 {{Задача
-|definition=Дано [[Основные определения теории графов#oriented_grath|ориентированный]] [[Дерево, эквивалентные определения#tree|дерево]], вершины которого раскрашены в цвета. Найти <tex>dc:V\rightarrow \{1\ldots k\}</tex>, где <tex>dc(u) -</tex> число различных цветов в поддереве с корнем в вершине <tex>u</tex>. Время работы: <tex>O(V)</tex>}}
+|definition=Дано [[Основные определения теории графов#oriented_grath|ориентированное]] [[Дерево, эквивалентные определения#tree|дерево]], вершины которого раскрашены в цвета. Найти <tex>dc:V\rightarrow \{1\ldots k\}</tex>, где <tex>dc(u) -</tex> число различных цветов в поддереве с корнем в вершине <tex>u</tex>. Время работы: <tex>O(V)</tex>}}
 __TOC__
 ==Алгоритм решения==
-Будем в каждой вершине дерева хранить по числу, так, чтобы для каждого поддерева ответом была сумма всех значений в вершинах в данном поддереве. Для начала каждой вершине в качестве значения присвоим <tex>1</tex>. Теперь, если бы все вершины имели различные цвета, надо было бы пройти снизу вверх по дереву и просуммировать для каждой вершины числа, записанные в её детях. Но некоторые вершины будут иметь одинаковые цвета, и это надо как-то учитывать. Для этого запустим [[Обход в глубину, цвета вершин|обход в глубину]]. Также будем хранить для каждого цвета последнюю посещенную вершину данного цвета в массиве <tex>last[k]</tex>. Теперь, заходя в <tex>i</tex>-ую вершину с цветом <tex>col</tex>, смотрим: если вершина с таким цветом еще не встречалась, то просто присваиваем <tex>last[col]=i</tex>, иначе, если вершина с данным цветом уже встречалась, то находим [[Сведение задачи LCA к задаче RMQ|наименьшего общего предка]] данной вершины и последней вершины с таким цветом и вычитаем из их предка <tex>1</tex>, присваиваем <tex>last[col]=i</tex>. Теперь при выходе из вершины можно просуммировать числа в ее детях и получить ответ для данной вершины, так как для нее все дети уже подсчитаны. Таким образом, алгоритм запускает один обход в глубину, на каждой итерации которого ищет наименьшего общего предка. Если искать наименьшего общего предка за <tex>O(1)</tex>, к примеру [[Алгоритм Фарака-Колтона и Бендера|алгоритмом Фарака-Колтона и Бендера]], то сложность работы алгоритма будет <tex>O(V)</tex>.
+Будем в каждой вершине дерева хранить по числу, так, чтобы для каждого поддерева ответом была сумма всех значений в вершинах в данном поддереве. Для начала каждой вершине в качестве значения присвоим <tex>1</tex>. Теперь, если бы все вершины имели различные цвета, надо было бы пройти снизу вверх по дереву и просуммировать для каждой вершины числа, записанные в её детях. Но некоторые вершины будут иметь одинаковые цвета, и это надо как-то учитывать.
 ==Пример==
@@ Строка 43: / Строка 50: @@
   '''func''' dfs('''Node''' v)''':'''
      used[v] = <b>true</b>
-     '''for''' <tex>u \in v.children</tex>
+     '''for''' <tex>u \in</tex> v.children
          '''if''' !used[u]
              dfs(u)
@@ Строка 70: / Строка 77: @@
 }}
-Для того, чтобы учитывать вершины с одинаковым цветом, для каждой вершины требуется найти наименьшего общего предка этой вершины и вершин, предшествующих данной по времени выхода с таким же цветом и вычесть из значения этого предка <tex>1</tex>. Так, при конечном подсчете значение наименьшего общего предка данной вершины и любой вершины, предшествующей данной с тем же цветом, уменьшится на <tex>1</tex>, так как наименьший предок этой точки и любой предшествующей того же цвета находится на пути из наименьшего общего предка этой группы точек. А как раз это и требуется - для каждой пары точек одного цвета учесть данный факт в их наименьшем общем предке. И по лемме, чтобы взять наименьшего общего предка текущей вершины и всех предшествующих вершин с данным цветом, надо взять наименьшего общего предка данной вершины и предыдущей вершины с данным цветом, он будет наименьшим для всех.
+Для того, чтобы учитывать вершины с одинаковым цветом, для каждой вершины требуется найти наименьшего общего предка этой вершины и вершин, предшествующих данной по времени выхода с таким же цветом и вычесть из значения этого предка <tex>1</tex>. Так, при конечном подсчете значение наименьшего общего предка данной вершины и любой вершины, предшествующей данной с тем же цветом, уменьшится на <tex>1</tex>, так как наименьший предок этой точки и любой предшествующей того же цвета находится на пути из наименьшего общего предка этой группы точек. А как раз это и требуется <tex>-</tex> для каждой пары точек одного цвета учесть данный факт в их наименьшем общем предке. И по лемме, чтобы взять наименьшего общего предка текущей вершины и всех предшествующих вершин с данным цветом, надо взять наименьшего общего предка данной вершины и предыдущей вершины с данным цветом, он будет наименьшим для всех.
 [[Файл:hugh.png|300px]]
 ==См. также==
-[[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]
+*[[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]
-[[Метод двоичного подъема]]
+*[[Метод двоичного подъема]]
 [[Категория: Алгоритмы и структуры данных]]

@@ Строка 1: / Строка 1: @@
 {{Задача
-|definition=Дано ориентированное дерево, вершины которого раскрашены в цвета. Найти <tex>dc:V\rightarrow \{1..k\}</tex>, где <tex>dc(u) -</tex> число различных цветов в поддереве с корнем в вершине <tex>u</tex>. Время работы: <tex>O(V)</tex>}}
+|definition=Дано [[Основные определения теории графов#oriented_grath|ориентированный]] [[Дерево, эквивалентные определения#tree|дерево]], вершины которого раскрашены в цвета. Найти <tex>dc:V\rightarrow \{1\ldots k\}</tex>, где <tex>dc(u) -</tex> число различных цветов в поддереве с корнем в вершине <tex>u</tex>. Время работы: <tex>O(V)</tex>}}
 __TOC__
 ==Алгоритм решения==
-Для начала в каждой вершине поставим 1. Теперь, если бы все вершины имели различные цвета, надо было бы пройти снизу вверх по дереву и просуммировать для каждой вершины числа, записанные в ее детях. Но некоторые вершины будут иметь одинаковые цвета, и это надо как-то учитывать. Для этого запустим [[Обход в глубину, цвета вершин|обход в глубину]]. Также будем хранить для каждого цвета последнюю посещенную вершину данного цвета в массиве <tex>last[k]</tex>. Теперь, заходя в <tex>i</tex>-ую вершину с цветом <tex>col</tex>, смотрим: если вершина с таким цветом еще не встречалась, то просто записываем в <tex>last[col]\ i</tex>, иначе, если вершина с данным цветом уже встречалась, то находим [[Сведение задачи LCA к задаче RMQ|наименьшего общего предка]] данной вершины и последней вершины с таким цветом и вычитаем из их предка 1, и записываем в <tex>last[col]\ i</tex>. Теперь при выходе из вершины можно просуммировать числа в ее детях и получить ответ для данной вершины, так как для нее все дети уже подсчитаны. Таким образом, алгоритм запускает один обход в глубину, на каждой итерации которого ищет наименьшего общего предка. Если искать наименьшего общего предка за <tex>O(1)</tex>, к примеру [[Алгоритм Фарака-Колтона и Бендера|алгоритмом Фарака-Колтона и Бендера]], то сложность работы алгоритма будет <tex>O(V)</tex>
+Будем в каждой вершине дерева хранить по числу, так, чтобы для каждого поддерева ответом была сумма всех значений в вершинах в данном поддереве. Для начала каждой вершине в качестве значения присвоим <tex>1</tex>. Теперь, если бы все вершины имели различные цвета, надо было бы пройти снизу вверх по дереву и просуммировать для каждой вершины числа, записанные в её детях. Но некоторые вершины будут иметь одинаковые цвета, и это надо как-то учитывать. Для этого запустим [[Обход в глубину, цвета вершин|обход в глубину]]. Также будем хранить для каждого цвета последнюю посещенную вершину данного цвета в массиве <tex>last[k]</tex>. Теперь, заходя в <tex>i</tex>-ую вершину с цветом <tex>col</tex>, смотрим: если вершина с таким цветом еще не встречалась, то просто присваиваем <tex>last[col]=i</tex>, иначе, если вершина с данным цветом уже встречалась, то находим [[Сведение задачи LCA к задаче RMQ|наименьшего общего предка]] данной вершины и последней вершины с таким цветом и вычитаем из их предка <tex>1</tex>, присваиваем <tex>last[col]=i</tex>. Теперь при выходе из вершины можно просуммировать числа в ее детях и получить ответ для данной вершины, так как для нее все дети уже подсчитаны. Таким образом, алгоритм запускает один обход в глубину, на каждой итерации которого ищет наименьшего общего предка. Если искать наименьшего общего предка за <tex>O(1)</tex>, к примеру [[Алгоритм Фарака-Колтона и Бендера|алгоритмом Фарака-Колтона и Бендера]], то сложность работы алгоритма будет <tex>O(V)</tex>.
-Пример:
+==Пример==
-Шаг 0:
+{| class = "wikitable"
-[[Файл:algo_0.png|200px]]
+! № шага !! Изображение !! Описание
+|-align="center"
-Шаг 1:
+| 0
-[[Файл:algo_1.png|200px]]
+| [[Файл:algo_0.png|300px]]
+| Расставим у каждой вершины <tex>1</tex>.
-Шаг 2:
+|-align="center"
-[[Файл:algo_2.png|200px]]
+| 1
+| [[Файл:algo_1.png|300px]]
-Шаг 3:
+| Выходим из <tex>8</tex>-ой вершины. Так как желтых вершин еще не было, запоминаем её как последнюю желтую.
-[[Файл:algo_3.png|200px]]
+|-align="center"
+| 2
-Шаг n:
+| [[Файл:algo_2.png|300px]]
-[[Файл:algo_n-1.png|200px]]
+| <tex>4</tex>-ая вершина. Последняя желтая <tex>-\ 8</tex>-ая. Их LCA <tex>\ -4</tex>-ая вершина. Вычитаем из значения <tex>4</tex>-ой вершины <tex>1</tex> и запоминаем текущую как последнюю желтую.
+|-align="center"
-Окончательное суммирование
+| 8
-[[Файл:algo_n.png|200px]]
+| [[Файл:8.png|300px]]
 ==Псевдокод==
-  '''func''' dfs (Node v)''':'''
+ '''int''' col[MAX_COL], used[MAX_N], sum[MAX_N]
-     used[v] := true
      '''for''' <tex>u \in v.children</tex>
          '''if''' !used[u]
              dfs(u)
-         sum[v] := sum[v] + sum[u]
+         sum[v] += sum[u]
      '''if''' last[col[v]] != -1
-          sum[lca(v, last[col[v]])] -= 1
+          sum[lca(v, last[col[v]])]--
-     last[col[v]] := v
+     last[col[v]] = v
-  '''func''' hugh (int n, int k, Node root)''':'''
+  '''func''' hugh('''int''' n, '''int''' k, '''Node''' root)''':'''
      '''for''' <tex>v \in V</tex>
-         used[v] := false
+         used[v] = <b>false</b>
-         sum[v] := 1
+         sum[v] = 1
-     '''for''' k := 1 to k
+     '''for''' i = 1 to k
-         last[k] := -1
+         last[i] = -1
-     dfs (root)
+     dfs(root)
 ==Обоснование корректности==
@@ Строка 57: / Строка 70: @@
 }}
-Для того, чтобы учитывать вершины с одинаковым цветом, для каждой вершины требуется найти наименьшего общего предка этой вершины и вершин, предшествующих данной по времени выхода с таким же цветом и вычесть из значения этого предка 1. Так, при конечном подсчете значение наименьшего общего предка данной вершины и любой вершины, предшествующей данной с тем же цветом, уменьшится на 1, так как наименьший предок этой точки и любой предшествующей того же цвета находится на пути из наименьшего общего предка этой группы точек. А как раз это и требуется - для каждой пары точек одного цвета учесть данный факт в их наименьшем общем предке. И по лемме, чтобы взять наименьшего общего предка текущей вершины и всех предшествующих вершин с данным цветом, надо взять наименьшего общего предка данной вершины и предыдущей вершины с данным цветом, он будет наименьшим для всех.
+Для того, чтобы учитывать вершины с одинаковым цветом, для каждой вершины требуется найти наименьшего общего предка этой вершины и вершин, предшествующих данной по времени выхода с таким же цветом и вычесть из значения этого предка <tex>1</tex>. Так, при конечном подсчете значение наименьшего общего предка данной вершины и любой вершины, предшествующей данной с тем же цветом, уменьшится на <tex>1</tex>, так как наименьший предок этой точки и любой предшествующей того же цвета находится на пути из наименьшего общего предка этой группы точек. А как раз это и требуется - для каждой пары точек одного цвета учесть данный факт в их наименьшем общем предке. И по лемме, чтобы взять наименьшего общего предка текущей вершины и всех предшествующих вершин с данным цветом, надо взять наименьшего общего предка данной вершины и предыдущей вершины с данным цветом, он будет наименьшим для всех.
 [[Файл:hugh.png|300px]]
 ==См. также==

← Предыдущая	Версия 10:34, 2 января 2016
(нет различий)