Изменения

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

used[v] = <b>''true</b>'' '''for''' <tex>u \in v.children</tex>v.children

used[v] = <b>''false</b>''

'''for''' i = 1 '''to ''' k

{{Лемма|statement = Наименьшим общим предком Отсортируем вершины и группы вершин, предшествующих по времени выхода, является наименьший общий предок данной вершины и последней, предшествующей ей из группывхода.|proof = Рассмотрим дерево как последовательность букв, когда при входе в вершину или выходе из нее записывается ее буква. Пусть рассматриваемая вершина <tex>-\ u</tex>, а последняя рассмотренная из той же группы <tex> -\ v</tex>, их наименьший общий предок в поддереве которой <tex>-\ wk</tex>. Рассмотрим два варианта расположения этих двух вершинодного цвета. [[Файл:proof_1.png|200px]][[Файл:proof_2.png|200px]] Теперь возьмем вершину <tex>z</tex>Так как мы обходим вершины в порядке времени входа, которая встречается до выхода из эти <tex>vk</tex>вершин мы обойдем последовательно. Перебрав несложные пять случаев, можно легко убедиться, что Их наименьший общий предок будет лежать в данном поддереве. Следовательно мы вычтем <tex>uk-1</tex> и раз единицу из вершины <tex>v</tex> будет ниже, чем наименьший общий предок <tex>u</tex> и <tex>x</tex>.}} Для того, чтобы учитывать вершины с одинаковым цветом, для каждой вершины требуется найти наименьшего общего предка этой вершины и любых других двух вершин, предшествующих данной по времени выхода с таким же цветом и вычесть из значения этого предка <tex>1</tex>. Так, при конечном подсчете значение наименьшего общего предка данной вершины и любой вершины, предшествующей данной с тем же цветом, уменьшится на <tex>1</tex>, так как их наименьший общий предок этой точки и любой предшествующей того же цвета находится на пути из наименьшего общего предка этой группы точекне будет лежать в данном поддереве. А как раз это и требуется - Следовательно для каждой пары точек одного каждого поддерева учтется по одной вершине каждого цвета учесть данный факт , существующего в их наименьшем общем предке. И по лемме, чтобы взять наименьшего общего предка текущей вершины и всех предшествующих вершин с данным цветом, надо взять наименьшего общего предка данной вершины и предыдущей вершины с данным цветом, он будет наименьшим для всех. [[Файл:hughданном поддереве.png|300px]]

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

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