50
правок
Изменения
м
Нет описания правки
==Простое решение==
Ответ на задачу можно получить достаточно просто с помощью битовых масок. Для начала в каждую вершину поместим битовую маску с цветом данной вершины. Запустим [[Обход в глубину, цвета вершин|обход в глубину]] и на выходе из каждой вершины будем записывать в неё результат побитового <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)
