Изменения

|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|наименьшего общего предка]] данной вершины и последней вершины с таким цветом и вычитаем из их предка 1, и записываем в <tex>last[col]\ i</tex>. Теперь при выходе из вершины можно просуммировать числа в ее детях и получить ответ для данной вершины, так как для нее все дети уже подсчитаны. Таким образом, алгоритм запускает один обход в глубину, на каждой итерации которого ищет наименьшего общего предка. Если искать наименьшего общего предка за <tex>O(1)</tex>, к примеру [[Алгоритм Фарака-Колтона и Бендера|алгоритмом Фарака-Колтона и Бендера]], то сложность работы алгоритма будет <tex>O(V)</tex> Пример: Шаг 0:[[Файл:algo_0.png|200px]]

Шаг 1Для этого запустим обход в глубину. Также будем хранить для каждого цвета последнюю посещенную вершину данного цвета в массиве <tex>last[k]</tex>. Теперь, заходя в <tex>i</tex>-ую вершину с цветом <tex>col</tex>, смотрим:если вершина с таким цветом еще не встречалась, то просто присваиваем <tex>last[col]=i</tex>, иначе, если вершина с данным цветом уже встречалась, то находим [[Файл:algo_1.pngСведение задачи LCA к задаче RMQ|200pxнаименьшего общего предка]]данной вершины и последней вершины с таким цветом и вычитаем из их предка <tex>1</tex>, присваиваем <tex>last[col]=i</tex>. Теперь при выходе из вершины можно просуммировать числа в ее детях и получить ответ для данной вершины, так как для нее все дети уже подсчитаны.

Шаг 2:Таким образом, алгоритм запускает один обход в глубину, на каждой итерации которого ищет наименьшего общего предка. Если искать наименьшего общего предка за <tex>O(1)</tex>, к примеру [[Файл:algo_2.pngАлгоритм Фарака-Колтона и Бендера|200pxалгоритмом Фарака-Колтона и Бендера]], то сложность работы алгоритма будет <tex>O(V)</tex>.

Шаг n{| 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_nalgo_2.png|300px]]| <tex>4</tex>-ая вершина. Последняя желтая <tex>-\ 8</tex>-ая. Их LCA <tex>\ -4</tex>-ая вершина. Вычитаем из значения <tex>4</tex>-ой вершины <tex>1</tex> и запоминаем текущую как последнюю желтую.|-align="center"| 8| [[Файл:8.png|200px300px]]| Пропустим несколько тривиальных шагов. Выходим из <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_nalgo_12.png|200px300px]]|Пропустим еще два шага. В результате суммирования получаем в каждой вершине ответ на задачу для поддерева.|-|}

'''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

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] := ''false'' sum[v] := 1 '''for''' k :i = 1 '''to ''' k last[ki] := -1 dfs (root)

{{Лемма|statement = Наименьшим общим предком Отсортируем вершины и группы вершин, предшествующих по времени выхода, является наименьший общий предок данной вершины и последней, предшествующей ей из группывхода.|proof = Рассмотрим дерево как последовательность букввершину <tex>v</tex>, когда при входе в вершину или выходе из нее записывается ее буква. Пусть рассматриваемая вершина поддереве которой <tex>-\ uk</tex>вершин одного цвета. Так как мы обходим вершины в порядке времени входа, а последняя рассмотренная из той же группы эти <tex> -\ vk</tex>, их вершин мы обойдем последовательно. Их наименьший общий предок будет лежать в данном поддереве. Следовательно мы вычтем <tex>k-\ w1</tex> раз единицу из вершины <tex>v</tex>. Рассмотрим два варианта расположения этих Для любых других двух вершиних наименьший общий предок не будет лежать в данном поддереве. Следовательно для каждого поддерева учтется по одной вершине каждого цвета, существующего в данном поддереве.

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

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

[[ФайлКатегория:hugh.png|300pxЗадача о наименьшем общем предке]] ==См. также==