Алгоритм Хьюи

2016-01-23T15:01:36Z

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

{{Задача
|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>OR</tex> масок её детей и её самой. Таким образом в каждой вершине будет храниться битовая маска с цветами, лежащими в данном поддереве. Общая сложность алгоритма будет <tex>O(V \cdot K)</tex>, где <tex>K\ -</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>.

==Пример==

{| class = "wikitable"
! № шага !! Изображение !! Описание
|-align="center"
| 0
| [[Файл:algo_0.png|300px]]
| Расставим у каждой вершины <tex>1</tex>.
|-align="center"
| 1
| [[Файл:algo_1.png|300px]]
| Выходим из <tex>8</tex>-ой вершины. Так как желтых вершин еще не было, запоминаем её как последнюю желтую.
|-align="center"
| 2
| [[Файл:algo_2.png|300px]]
| <tex>4</tex>-ая вершина. Последняя желтая <tex>-\ 8</tex>-ая. Их LCA <tex>\ -4</tex>-ая вершина. Вычитаем из значения <tex>4</tex>-ой вершины <tex>1</tex> и запоминаем текущую как последнюю желтую.
|-align="center"
| 8
| [[Файл:8.png|300px]]
| Пропустим несколько тривиальных шагов. Выходим из <tex>11</tex>-ой вершины. Последней посещенной зеленой была <tex>5</tex>-ая (не <tex>3</tex>-я). Вычитаем из их LCA (<tex>1</tex>-ой вершины) <tex>1</tex> и запоминаем <tex>11</tex>-ую как последнюю зеленую.
|-align="center"
| 9
| [[Файл:9.png|300px]]
| Выходим из <tex>7</tex>-ой вершины. Последней синей была <tex>2</tex>-ая. Вычтем из их LCA <tex>1</tex> и запомним <tex>7</tex>-ую как последнюю синюю.
|-align="center"
| суммирование
| [[Файл:algo_12.png|300px]]
|Пропустим еще два шага. В результате суммирования получаем в каждой вершине ответ на задачу для поддерева.
|-
|}

==Псевдокод==
'''int''' col[MAX_COL], used[MAX_N], sum[MAX_N]

'''func''' dfs('''Node''' v)''':'''
used[v] = ''true''
'''for''' <tex>u \in</tex> 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''' <tex>v \in V</tex>
used[v] = ''false''
sum[v] = 1
'''for''' i = 1 '''to''' k
last[i] = -1
dfs(root)

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

==См. также==
*[[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]

*[[Метод двоичного подъема]]

[[Категория: Алгоритмы и структуры данных]]

[[Категория: Задача о наименьшем общем предке]]

Викиконспекты - Вклад участника [ru]

Алгоритм Хьюи