Изменения
→Обоснование корректности
{{Задача
|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|наименьшего общего предка]] данной вершины и последней вершины с таким цветом и вычитаем из их предка 1, и записываем в <tex>last[col]\ i</tex>. Теперь при выходе из вершины можно просуммировать числа в ее детях и получить ответ для данной вершины, так как для нее все дети уже подсчитаны. Таким образом, алгоритм запускает один обход в глубину, на каждой итерации которого ищет наименьшего общего предка. Если искать наименьшего общего предка за <tex>O(1)</tex>, к примеру [[Алгоритм Фарака-Колтона и Бендера|алгоритмом Фарака-Колтона и Бендера]], то сложность работы алгоритма будет <tex>O(V)</tex> Пример: Шаг 0:[[Файл:algo_0.png|200px]]
==Псевдокод==
'''int''' col[MAX_COL], used[MAX_N], sum[MAX_N] '''func''' dfs ('''Node ''' v)''':''' used[v] := ''true'' '''for''' <tex>u \in v.children</tex>v.children
'''if''' !used[u]
dfs(u)
sum[v] :+= sum[v] + sum[u]
'''if''' last[col[v]] != -1
sum[lca(v, last[col[v]])] -= 1- 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''' k :i = 1 '''to ''' k last[ki] := -1 dfs (root)
==Обоснование корректности==
[[ФайлКатегория:hugh.png|300pxЗадача о наименьшем общем предке]] ==См. также==