Изменения

{{Лемма|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]]