Изменения

|definition=Дано ориентированное [[Основные определения теории графов#oriented_grath|ориентированный]] [[Дерево, эквивалентные определения#tree|дерево]], вершины которого раскрашены в цвета. Найти <tex>dc:V\rightarrow \{1..\ldots k\}</tex>, где <tex>dc(u) -</tex> число различных цветов в поддереве с корнем в вершине <tex>u</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|200px300px]]| Расставим у каждой вершины <tex>1</tex>.Шаг |-align="center"| 1:| [[Файл:algo_1.png|200px300px]]| Выходим из <tex>8</tex>-ой вершины. Так как желтых вершин еще не было, запоминаем её как последнюю желтую.|-align="center"Шаг | 2:| [[Файл:algo_2.png|200px300px]]| <tex>4</tex>-ая вершина. Последняя желтая <tex>-\ 8</tex>-ая. Их LCA <tex>\ -4</tex>-ая вершина. Вычитаем из значения <tex>4</tex>-ой вершины <tex>1</tex> и запоминаем текущую как последнюю желтую.Шаг 3:|-align="center"| 8| [[Файл:algo_38.png|200px300px]]| Пропустим несколько тривиальных шагов. Выходим из <tex>11</tex>-ой вершины. Последней посещенной зеленой была <tex>5</tex>-ая (не <tex>3</tex>-я). Вычитаем из их LCA (<tex>1</tex>-ой вершины) <tex>1</tex> и запоминаем <tex>11</tex>-ую как последнюю зеленую.|-align="center"Шаг n:| 9| [[Файл:algo_n-19.png|200px300px]]| Выходим из <tex>7</tex>-ой вершины. Последней синей была <tex>2</tex>-ая. Вычтем из их LCA <tex>1</tex> и запомним <tex>7</tex>-ую как последнюю синюю.|-align="center"Окончательное | суммирование| [[Файл:algo_nalgo_12.png|200px300px]]|Пропустим еще два шага. В результате суммирования получаем в каждой вершине ответ на задачу для поддерева.|-|}

'''int''' col[MAX_COL], used[MAX_N], sum[MAX_N] '''func''' dfs ('''Node ''' v)''':''' used[v] := <b>true</b>

sum[v] :+= sum[v] + sum[u]

sum[lca(v, last[col[v]])] -= 1- last[col[v]] := v

'''func''' hugh ('''int ''' n, '''int ''' k, '''Node ''' root)''':'''

used[v] := <b>false</b> sum[v] := 1 '''for''' k :i = 1 to k last[ki] := -1 dfs (root)

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