Алгоритм Хьюи

Задача:

Дано ориентированное дерево, вершины которого раскрашены в цвета. Найти [math]dc:V\rightarrow \{1..k\}[/math], где [math]dc(u) -[/math] число различных цветов в поддереве с корнем в вершине [math]u[/math]. Время работы: [math]O(V)[/math]

Алгоритм решения

Для начала в каждой вершине поставим 1. Теперь, если бы все вершины имели различные цвета, надо было бы пройти снизу вверх по дереву и просуммировать для каждой вершины числа, записанные в ее детях. Но некоторые вершины будут иметь одинаковые цвета, и это надо как-то учитывать. Для этого запустим обход в глубину. Также будем хранить для каждого цвета последнюю посещенную вершину данного цвета в массиве [math]last[k][/math]. Теперь, заходя в [math]i[/math]-ую вершину с цветом [math]col[/math], смотрим: если вершина с таким цветом еще не встречалась, то просто записываем в [math]last[col]\ i[/math], иначе, если вершина с данным цветом уже встречалась, то находим наименьшего общего предка данной вершины и последней вершины с таким цветом и вычитаем из их предка 1, и записываем в [math]last[col]\ i[/math]. Теперь при выходе из вершины можно просуммировать числа в ее детях и получить ответ для данной вершины, так как для нее все дети уже подсчитаны. Таким образом, алгоритм запускает один обход в глубину, на каждой итерации которого ищет наименьшего общего предка. Если искать наименьшего общего предка за [math]O(1)[/math], к примеру алгоритмом Фарака-Колтона и Бендера, то сложность работы алгоритма будет [math]O(V)[/math]

Пример:

Шаг 0:

Шаг 1:

Шаг 2:

Шаг 3:

Шаг n:

Окончательное суммирование

Псевдокод

func dfs (Node v):
   used[v] := true
   for [math]u \in v.children[/math]
       if !used[u]
           dfs(u)
       sum[v] := sum[v] + sum[u]
   if last[col[v]] != -1
        sum[lca(v, last[col[v]])] -= 1
   last[col[v]] := v
       
func hugh (int n, int k, Node root):
   for [math]v \in V[/math]
       used[v] := false
       sum[v] := 1
   for k := 1 to k
       last[k] := -1
   dfs (root)

Обоснование корректности

Лемма:

Наименьшим общим предком вершины и группы вершин, предшествующих по времени выхода, является наименьший общий предок данной вершины и последней, предшествующей ей из группы.

Доказательство:

[math]\triangleright[/math]

Рассмотрим дерево как последовательность букв, когда при входе в вершину или выходе из нее записывается ее буква. Пусть рассматриваемая вершина [math]-\ u[/math], а последняя рассмотренная из той же группы [math] -\ v[/math], их наименьший общий предок [math]-\ w[/math]. Рассмотрим два варианта расположения этих двух вершин. Теперь возьмем вершину [math]z[/math], которая встречается до выхода из [math]v[/math]. Перебрав несложные пять случаев, можно легко убедиться, что наименьший общий предок [math]u[/math] и [math]v[/math] будет ниже, чем наименьший общий предок [math]u[/math] и [math]x[/math].

[math]\triangleleft[/math]

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