==Простое решение==
Ответ на задачу можно получить достаточно просто с помощью битовых масок. Для начала в каждую вершину поместим битовую маску с цветом данной вершины. Запустим [[Обход в глубину, цвета вершин|обход в глубину]] и на выходе из каждой вершины будем записывать в неё результат побитового <tex>OR</tex> масок её детей и её самой. Таким образом в каждой вершине будет храниться битовая маска с цветами, лежащими в данном поддереве. Общая сложность алгоритма будет <tex>O(V \cdot K)</tex>, где <tex>K\ -</tex> количество цветов. Если количество цветов меньше размера машинного слова, то сложность будет составит <tex>O(V)</tex>.
==Алгоритм решения==
'''func''' dfs('''Node''' v)''':'''
used[v] = <b>''true</b>''
'''for''' <tex>u \in</tex> v.children
'''if''' !used[u]
'''func''' hugh('''int''' n, '''int''' k, '''Node''' root)''':'''
'''for''' <tex>v \in V</tex>
used[v] = <b>''false</b>''
sum[v] = 1
'''for''' i = 1 '''to ''' k
last[i] = -1
dfs(root)
==Обоснование корректности==
{{Лемма|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>, так как их наименьший общий предок этой точки и любой предшествующей того же цвета находится на пути из наименьшего общего предка этой группы точекне будет лежать в данном поддереве. А как раз это и требуется <tex>-</tex> Следовательно для каждой пары точек одного каждого поддерева учтется по одной вершине каждого цвета учесть данный факт , существующего в их наименьшем общем предке. И по лемме, чтобы взять наименьшего общего предка текущей вершины и всех предшествующих вершин с данным цветом, надо взять наименьшего общего предка данной вершины и предыдущей вершины с данным цветом, он будет наименьшим для всех. [[Файл:hughданном поддереве.png|300px]]
==См. также==
