Алгоритм Хьюи — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Обоснование корректности)
Строка 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>}}

Версия 07:07, 1 сентября 2022

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.

Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.

Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.

Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.

Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.


Задача:
Дано ориентированное дерево, вершины которого раскрашены в цвета. Найти [math]dc:V\rightarrow \{1\ldots k\}[/math], где [math]dc(u) -[/math] число различных цветов в поддереве с корнем в вершине [math]u[/math]. Время работы: [math]O(V)[/math]


Простое решение

Ответ на задачу можно получить достаточно просто с помощью битовых масок. Для начала в каждую вершину поместим битовую маску с цветом данной вершины. Запустим обход в глубину и на выходе из каждой вершины будем записывать в неё результат побитового [math]OR[/math] масок её детей и её самой. Таким образом в каждой вершине будет храниться битовая маска с цветами, лежащими в данном поддереве. Общая сложность алгоритма будет [math]O(V \cdot K)[/math], где [math]K\ -[/math] количество цветов. Если количество цветов меньше размера машинного слова, то сложность составит [math]O(V)[/math].

Алгоритм решения

Будем в каждой вершине дерева хранить по числу, так, чтобы для каждого поддерева ответом была сумма всех значений в вершинах в данном поддереве. Для начала каждой вершине в качестве значения присвоим [math]1[/math]. Теперь, если бы все вершины имели различные цвета, надо было бы пройти снизу вверх по дереву и просуммировать для каждой вершины числа, записанные в её детях. Но некоторые вершины будут иметь одинаковые цвета, и это надо как-то учитывать.

Для этого запустим обход в глубину. Также будем хранить для каждого цвета последнюю посещенную вершину данного цвета в массиве [math]last[k][/math]. Теперь, заходя в [math]i[/math]-ую вершину с цветом [math]col[/math], смотрим: если вершина с таким цветом еще не встречалась, то просто присваиваем [math]last[col]=i[/math], иначе, если вершина с данным цветом уже встречалась, то находим наименьшего общего предка данной вершины и последней вершины с таким цветом и вычитаем из их предка [math]1[/math], присваиваем [math]last[col]=i[/math]. Теперь при выходе из вершины можно просуммировать числа в ее детях и получить ответ для данной вершины, так как для нее все дети уже подсчитаны.

Таким образом, алгоритм запускает один обход в глубину, на каждой итерации которого ищет наименьшего общего предка. Если искать наименьшего общего предка за [math]O(1)[/math], к примеру алгоритмом Фарака-Колтона и Бендера, то сложность работы алгоритма будет [math]O(V)[/math].

Пример

№ шага Изображение Описание
0 Algo 0.png Расставим у каждой вершины [math]1[/math].
1 Algo 1.png Выходим из [math]8[/math]-ой вершины. Так как желтых вершин еще не было, запоминаем её как последнюю желтую.
2 Algo 2.png [math]4[/math]-ая вершина. Последняя желтая [math]-\ 8[/math]-ая. Их LCA [math]\ -4[/math]-ая вершина. Вычитаем из значения [math]4[/math]-ой вершины [math]1[/math] и запоминаем текущую как последнюю желтую.
8 8.png Пропустим несколько тривиальных шагов. Выходим из [math]11[/math]-ой вершины. Последней посещенной зеленой была [math]5[/math]-ая (не [math]3[/math]-я). Вычитаем из их LCA ([math]1[/math]-ой вершины) [math]1[/math] и запоминаем [math]11[/math]-ую как последнюю зеленую.
9 9.png Выходим из [math]7[/math]-ой вершины. Последней синей была [math]2[/math]-ая. Вычтем из их LCA [math]1[/math] и запомним [math]7[/math]-ую как последнюю синюю.
суммирование Algo 12.png Пропустим еще два шага. В результате суммирования получаем в каждой вершине ответ на задачу для поддерева.

Псевдокод

int col[MAX_COL], used[MAX_N], sum[MAX_N]

func dfs(Node v):
   used[v] = true
   for [math]u \in[/math] v.children
       if !used[u]
           dfs(u)
       sum[v] += sum[u]
   if last[col[v]] != -1
        sum[lca(v, last[col[v]])]--
   last[col[v]] = v
       
func hugh(int n, int k, Node root):
   for [math]v \in V[/math]
       used[v] = false
       sum[v] = 1
   for i = 1 to k
       last[i] = -1
   dfs(root)

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

Отсортируем вершины по времени входа. Рассмотрим вершину [math]v[/math], в поддереве которой [math]k[/math] вершин одного цвета. Так как мы обходим вершины в порядке времени входа, эти [math]k[/math] вершин мы обойдем последовательно. Их наименьший общий предок будет лежать в данном поддереве. Следовательно мы вычтем [math]k-1[/math] раз единицу из вершины [math]v[/math]. Для любых других двух вершин их наименьший общий предок не будет лежать в данном поддереве. Следовательно для каждого поддерева учтется по одной вершине каждого цвета, существующего в данном поддереве.

См. также