Всем привет!
Не так давно я решил задачу 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)
? Если да, то как её решить с более лучшей асимптотикой?
А, ты перенумеровал вершины, был не прав в первой правке.
крутой хак
Из этого видно что расстояние между соседними вершинами будет примерно 3-4
Помоему, совсем не видно. В следующем графе это точно не выполняется: 1-2, 2-3, 2-4, 2-5, ..., 2-n. Если я правильно тебя понял, то порядок обхода будет такой: 2 3 4 5 ... n 1. Помоему, тут расстояние между соседними совсем не O(1), а O(N).
Я понял, что вы не поняли:)
Вы говорите про разницу позиций в обходе.
Я имел ввиду про расстояние между двумя вершинами в дереве, которые соседи в обходе.
То есть dist(v[i],v[i+1) = O(1). Где v[] — обход.
Похоже я чепуху сказал, потому что в эйлеров обходе будут встречаться лишние вершины между нашими искомыми, а их учитывать не надо.
Извините я тут ерунду написал.
Нельзя посчитать количество различных чисел на пути с помощью HLD. HLD по сути разбивает дерево на непересекающиеся по вершинам пути, и если мы просто возьмем путь (u, v) и разобьем его на части, каким образом мы сможем "скомбинировать" разные ответы от разных деревьев отрезков, отвечающих за эти части? Вдруг когда мы поднимаемся от v до u мы взяли ответ для текущего пути, а на следующем встречаются ровно те же числа? Мы не можем их просто суммировать.
Вы меня не поняли. Мы считаем сумму значений на пути. Там описывается значений каких.
Вас вообще сложно понять. Вот стоим например в корне, у него запрос это 2 любые достаточно отдаленные вершины, lca которых является корнем. Каким образом вы собираетесь с помощью HLD просуммировать a[v] на пути от корня до некоторой u? Причем то, что вы делаете и называется количеством различных чисел на пути.
Всё спасибо я вас понял. Я лось.