50
правок
Изменения
Новая страница: «{{Задача |definition=Дано ориентированное дерево, вершины которого раскрашены в цвета. Найти <t...»
{{Задача
|definition=Дано ориентированное дерево, вершины которого раскрашены в цвета. Найти <tex>dc:V\rightarrow \{1..k\}</tex>, где <tex>dc(u) -</tex> число различных цветов в поддереве с корнем в вершине <tex>u</tex>. Время работы: <tex>O(V)</tex>}}
__TOC__
==Алгоритм решения==
Для начала в каждой вершине поставим единицу. Теперь, если бы все вершины имели различные цвета, надо было бы пройти снизу вверх по дереву и просуммировать для каждой вершины числа, записанные в ее детях. Но некоторые вершины будут иметь одинаковые цвета, и это надо как-то учитывать. Для этого запустим обход в глубину. Также будем хранить для каждого цвета последнюю посещенную вершину данного цвета в массиве <tex>last[k]</tex>. Теперь, заходя в <tex>i</tex>-ую вершину с цветом <tex>col</tex>, смотрим: если вершина с таким цветом еще не встречалась, то просто записываем в <tex>last[col]\ i</tex>, иначе, если вершина с данным цветом уже встречалась, то находим наименьшего общего предка данной вершины и последней вершины с таким цветом и вычитаем из их предка 1, и записываем в <tex>last[col]\ i</tex>. Теперь при выходе из вершины можно просуммировать числа в ее детях и получить ответ для данной вершины, так как для нее все дети уже подсчитаны.
Пример:
Шаг 0:
[[Файл:algo_0.png|200px]]
Шаг 1:
[[Файл:algo_1.png|200px]]
Шаг 2:
[[Файл:algo_2.png|200px]]
Шаг 3:
[[Файл:algo_3.png|200px]]
Шаг n:
[[Файл:algo_n-1.png|200px]]
Окончательное суммирование
[[Файл:algo_n.png|200px]]
==Псевдокод==
'''func''' dfs (Node v)''':'''
used[v] := true
'''for''' <tex>u \in v.children</tex>
'''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''' <tex>v \in V</tex>
used[v] := false
sum[v] := 1
'''for''' k := 1 to k
last[k] := -1
dfs (root)
==Обоснование корректности==
{{Лемма
|statement = Наименьшим общим предком вершины и группы вершин, предшествующих по времени выхода, является наименьший общий предок данной вершины и последней, предшествующей ей из группы.
|proof = Рассмотрим дерево как последовательность букв, когда при входе в вершину или выходе из нее записывается ее буква. Пусть рассматриваемая вершина <tex>-\ u</tex>, а последняя рассмотренная из той же группы <tex> -\ v</tex>, их наименьший общий предок <tex>-\ w</tex> Рассмотрим два варианта расположения этих двух вершин.
[[Файл:proof_1.png|200px]]
[[Файл:proof_2.png|200px]]
Теперь возьмем вершину <tex>z</tex>, которая встречается до выхода из <tex>v</tex>. Перебрав несложные пять случаев, можно легко убедиться, что наименьший общий предок <tex>u</tex> и <tex>v</tex> будет ниже, чем наименьший общий предок <tex>u</tex> и <tex>x</tex>.
}}
Для того, чтобы учитывать две вершины с одинаковым цветом, для каждой вершины требуется найти наименьшего общего предка этой вершины и вершин, предшествующих данной по времени выхода с таким же цветом и вычесть из значения этого предка 1. Так, при конечном подсчете значение наименьшего общего предка данной вершины и любой вершины, предшествующей данной с тем же цветом, уменьшится на единицу, так как наименьший предок этой точки и любой предшествующей того же цвета находится на пути из наименьшего общего предка всех этих вершин до корня. А как раз это и требуется - для каждой пары точек одного цвета учесть данный факт в их наименьшем общем предке. И по лемме, чтобы взять наименьшего общего предка текущей вершины и всех предшествующих вершин с данным цветом, надо взять наименьшего общего предка данной вершины и предыдущей вершины с данным цветом, он будет наименьшим для всех.
[[Файл:hugh.png|300px]]
|definition=Дано ориентированное дерево, вершины которого раскрашены в цвета. Найти <tex>dc:V\rightarrow \{1..k\}</tex>, где <tex>dc(u) -</tex> число различных цветов в поддереве с корнем в вершине <tex>u</tex>. Время работы: <tex>O(V)</tex>}}
__TOC__
==Алгоритм решения==
Для начала в каждой вершине поставим единицу. Теперь, если бы все вершины имели различные цвета, надо было бы пройти снизу вверх по дереву и просуммировать для каждой вершины числа, записанные в ее детях. Но некоторые вершины будут иметь одинаковые цвета, и это надо как-то учитывать. Для этого запустим обход в глубину. Также будем хранить для каждого цвета последнюю посещенную вершину данного цвета в массиве <tex>last[k]</tex>. Теперь, заходя в <tex>i</tex>-ую вершину с цветом <tex>col</tex>, смотрим: если вершина с таким цветом еще не встречалась, то просто записываем в <tex>last[col]\ i</tex>, иначе, если вершина с данным цветом уже встречалась, то находим наименьшего общего предка данной вершины и последней вершины с таким цветом и вычитаем из их предка 1, и записываем в <tex>last[col]\ i</tex>. Теперь при выходе из вершины можно просуммировать числа в ее детях и получить ответ для данной вершины, так как для нее все дети уже подсчитаны.
Пример:
Шаг 0:
[[Файл:algo_0.png|200px]]
Шаг 1:
[[Файл:algo_1.png|200px]]
Шаг 2:
[[Файл:algo_2.png|200px]]
Шаг 3:
[[Файл:algo_3.png|200px]]
Шаг n:
[[Файл:algo_n-1.png|200px]]
Окончательное суммирование
[[Файл:algo_n.png|200px]]
==Псевдокод==
'''func''' dfs (Node v)''':'''
used[v] := true
'''for''' <tex>u \in v.children</tex>
'''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''' <tex>v \in V</tex>
used[v] := false
sum[v] := 1
'''for''' k := 1 to k
last[k] := -1
dfs (root)
==Обоснование корректности==
{{Лемма
|statement = Наименьшим общим предком вершины и группы вершин, предшествующих по времени выхода, является наименьший общий предок данной вершины и последней, предшествующей ей из группы.
|proof = Рассмотрим дерево как последовательность букв, когда при входе в вершину или выходе из нее записывается ее буква. Пусть рассматриваемая вершина <tex>-\ u</tex>, а последняя рассмотренная из той же группы <tex> -\ v</tex>, их наименьший общий предок <tex>-\ w</tex> Рассмотрим два варианта расположения этих двух вершин.
[[Файл:proof_1.png|200px]]
[[Файл:proof_2.png|200px]]
Теперь возьмем вершину <tex>z</tex>, которая встречается до выхода из <tex>v</tex>. Перебрав несложные пять случаев, можно легко убедиться, что наименьший общий предок <tex>u</tex> и <tex>v</tex> будет ниже, чем наименьший общий предок <tex>u</tex> и <tex>x</tex>.
}}
Для того, чтобы учитывать две вершины с одинаковым цветом, для каждой вершины требуется найти наименьшего общего предка этой вершины и вершин, предшествующих данной по времени выхода с таким же цветом и вычесть из значения этого предка 1. Так, при конечном подсчете значение наименьшего общего предка данной вершины и любой вершины, предшествующей данной с тем же цветом, уменьшится на единицу, так как наименьший предок этой точки и любой предшествующей того же цвета находится на пути из наименьшего общего предка всех этих вершин до корня. А как раз это и требуется - для каждой пары точек одного цвета учесть данный факт в их наименьшем общем предке. И по лемме, чтобы взять наименьшего общего предка текущей вершины и всех предшествующих вершин с данным цветом, надо взять наименьшего общего предка данной вершины и предыдущей вершины с данным цветом, он будет наименьшим для всех.
[[Файл:hugh.png|300px]]
