Всем привет!

Не так давно я решил задачу COT2.

В этой задаче нам дано дерево. Каждому дереву соответствует число. Нужно быстро отвечать на запрос x y — кол-во различных чисел на пути от вершины x до вершины y.

Сначала я написал на неё, как мне казалось верное решение, но оно было не верным, но оно зашло.

Вот это решение — http://pastie.org/8667428.

Идея его была такова:

Обойдем дерево dfs'ом и сохраним все вершины в порядке обхода. Обход назовем v[]. Потом чуть переделаем наши запросы:

Вместо (x,y) будет (l,r), где l и r позиции вершин x и y в нашем обходе v[]. Если l>r, то поменяем l и r местами.

Теперь применим корневую эвристику к запросам, то есть отсортируем запросы по паре (l/block,r), где block ~ sqrt(n).

Теперь будем обрабатывать наши запросы в отсортированном порядке.

То есть, если мы сейчас на пути v[old_l]->v[old_r] и нам надо перейти на путь v[l]->v[r], то мы просто двигаемся по дереву от вершины old_l до вершины l и от вершины old_r до вершины r. При этом, каждый раз посещая какую-нибудь вершину, мы проверяем: лежит ли она на пути v[l]->v[r], если лежит, то проверяем ложили ли мы число этой вершины в ответ, если нет, то ложим(ложить будем числа за O(1) применяя обычный массив меток).

Это есть мое первое решение. Оно зашло, хоть оно неверное. Так как для него есть хороший контр-тест, который дает асимптотику O(N*M).

Этот тест будет таким:

    1
   /|\
  / 2 \
 |     |
 |     |
 .     .
 .     .
 .     .
(n/2) (n)

А запросы будут такого вида:

(n/2,n/2+1), (2,n/2+2), (n/2,n/2+3), ..., (2,n)

Это будет худшим случаем для данного решения, так как мы построим такой обход:

v[]={ 1, 3, 4, 5, ..., n/2, 2, n/2+1, n/2+2, ..., n }

И вершины n/2 и 2 будут находиться рядом, но вот расстояние между ними будет O(N), и если мы будем обрабатывать запросы, в которых мы должны будем переходить на такое расстояние, то будет сложность решения O(N*M).

Но чуть позже я придумал верное решение. Оно отличается от первого решения совсем немного.

Вот код этого решения — http://pastie.org/8667490.

Мы должны поменять обход, чтобы расстояние между соседними вершинами в обходе было O(1). То есть dist(v[i],v[i+1])=O(1).

Делать будем его так:

Почти так же, как и обычный обход.

Будем ходить dfs'ом по дереву, когда заходим в вершину, то добавляем её в обход, если она на четной глубине. Когда выходим из вершины, то добавляем её в обход, если она на нечетной глубине.

Из этого видно что расстояние между соседними вершинами будет примерно 3-4, то есть dist(v[i],v[i+1])=O(1).

И мы получаем честное решение за O(M sqrt N).

Можете рассматривать эту мини-статейку, как разбор к этой задаче :)

Но у меня есть вопрос: Можно ли решить эту задачу с более лучшей асимптотикой, например O(M log N) или O(M log^2 N)? Если да, то как её решить с более лучшей асимптотикой?