Учитывая дерево, найти k-й узел на пути от узла «a» до узла «b» в журнале (n)?

Учитывая дерево, мне нужно найти «k-й узел на пути от «a» до «b». Это означает, что мне нужно найти узел в «k-м» положении на пути от узла «a» до узла «b». Я думал о линиях низшего общего предка и / или разложения тяжелого света, но я не уверен, что это способ сделать это. Приветствуется любое руководство в правильном направлении.

Подробности:

  • Дерево НЕ является бинарным деревом. Это неориентированный граф с n-1 ребрами, n вершинами и без циклов. Просто ваше обычное дерево
  • Дерево имеет вершины, пронумерованные от 1 до n. Существует n-1 неориентированных ребер, соединяющих n-1 пару этих вершин.
  • «a» и «b» — любые 2 вершины, пронумерованные в дереве от 1 до n. Нам нужно найти k-й узел на пути от a до b. Гарантируется, что значение «k» равно ‹= количеству узлов на пути от «a» до «b».

BFS, применяемая к каждому запросу (k-й узел от «a» до «b»), не подходит, поскольку количество запросов велико.


algorithm decomposition lowest-common-ancestor
person bholagabbar    schedule 25.01.2016    source источник
comment
Кажется очень тривиальным, поэтому, вероятно, это не то, для чего предназначена проблема, но, если путь задан, не можете ли вы просто отслеживать встречающиеся узлы, начиная с «a» и считая их до k-й?   -  person Matteo Di Napoli    schedule 25.01.2016
comment
O (журнал (n)) запрос? К вашему сведению, путь не «дан». В дереве существует только 1 путь между любыми 2 парами вершин.   -  person bholagabbar    schedule 25.01.2016
comment
Ваш вопрос начинается с заданного пути. И да, я бы сказал, что в дереве путь между двумя узлами уникален, иначе это не дерево.   -  person Matteo Di Napoli    schedule 25.01.2016
comment
Исправлена. Даны дерево и n-1 ребер с вершинами.   -  person bholagabbar    schedule 25.01.2016
comment
Это бинарное дерево, бинарное дерево поиска или дерево общего назначения? Вы знаете, где a и b в тройке? Узел дерева уже определен или вы можете его изменить? Можете ли вы предоставить образец ввода и ожидаемый результат?   -  person Fede    schedule 25.01.2016
comment
Я обновил вопрос. Это более ясно?   -  person bholagabbar    schedule 25.01.2016
comment
Неужели вопрос не ясен? Мне нужно найти узел в позиции «k» на пути от узла «a» до узла «b».   -  person bholagabbar    schedule 25.01.2016
comment
Я просто не понимаю акцент на k-м узле. В моем понимании найти путь от a до b — сложная задача (но в то же время гораздо более распространенная проблема), и если у вас есть этот путь, получить k-й элемент довольно тривиально, не так ли?   -  person tobias_k    schedule 25.01.2016
comment
Вот в чем дело. У меня нет «пути». Кроме того, я не уверен, что dfs / bfs каждый раз будет проходить, поскольку ограничения довольно жесткие.   -  person bholagabbar    schedule 25.01.2016
comment
Ответ был тем, что я искал. Кроме того, я упомянул log(n) на запрос в первом комментарии. В любом случае спасибо   -  person bholagabbar    schedule 25.01.2016

Ответы (1)


arrow_upward
2
arrow_downward

Сделайте самого низкого общего предка и сохраните для каждого узла его глубину (расстояние до корня).

Затем выясните, находится ли k-й узел в части от a до lca или от lca до b. Разница в глубине — это количество узлов между ними, поэтому, если depth[a] - depth[lca] > k, то узел находится на части lca-b.

Если узел находится в части от a до lca, просто найдите k-го предка a. Должен быть log(N) с использованием предварительно рассчитанных вами данных LCA.

Если узел находится в части от b до lca, то вы можете вычислить k', которое является расстоянием k-го узла от b (k' = 1 + depth[a] + depth[b] - 2*depth[lca] - k)), а затем получить k' предка b (опять же легко с данными LCA).

В целом, все поиски — это logN, а другие шаги постоянны, поэтому вы делаете O (LogN) для каждого запроса.

person Sorin    schedule 25.01.2016
comment
Да, это кажется законным. Спасибо! - person bholagabbar; 25.01.2016
comment
Я думаю, вам следует исправить «dapth» на «deep». Просто говорю хД - person bholagabbar; 25.01.2016
comment
@bholagabbar Исправлено. Я подозреваю, что мне также может понадобиться добавить 1 где-то. - person Sorin; 25.01.2016
comment
Я ошибся в вычислении k'. Количество узлов на пути от a к be должно быть 1+ значение там, и вы должны вычесть из него k. - person Sorin; 25.01.2016
comment
Спасибо. Предполагая, что я правильно заполнил массив pa[][], можете ли вы сказать мне, где это неправильно? Кажется, возвращается -1. pa[i][j] хранит 2^го родителя узла j ideone.com/slvLjA - person bholagabbar; 25.01.2016