Изменения

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

|proof = Рассмотрим дерево как последовательность букв, когда при входе в вершину или выходе из нее записывается ее буква. Пусть рассматриваемая вершина <tex>-\ u</tex>, а последняя рассмотренная из той же группы <tex> -\ v</tex>, их наименьший общий предок <tex>-\ w</tex> . Рассмотрим два варианта расположения этих двух вершин.

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