Тема: timus 1752
Здравствуйте!
http://acm.timus.ru/problem.aspx?space=1&num=1752
Собственно сабж. Вообще не представляю как решить за разумное время (естественно не перебор)...
Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Problems » timus 1752
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Здравствуйте!
http://acm.timus.ru/problem.aspx?space=1&num=1752
Собственно сабж. Вообще не представляю как решить за разумное время (естественно не перебор)...
Для каждой вершины найдем самую отдаленную от нее. Затем если d больше расстояния до самой удаленной вершины от v, то искомой u не существует. Иначе будем искать u на пути от v до самой удаленной (назовем ее w).
Если путь от v до w идет вниз (по направлению от корня к листьям), высота v равна v_h, а высота w равна w_h, то нам нужно найти вершину с номером d-v_h+w_h на пути от w к корню. Это можно сделать, предпосчитав для каждой вершины 1-го, 2-го, 4-го, 8-го и т.д. предков. Если же на пути от v к w мы в начале поднимаемся вверх, а потом спускаемся, то нам нужно либо найти предка v с высотой v_h-b, либо же если b>v_h, то предка w с высотой w_h-b+v_h-l_h, где l_h - высота LCA(v,w).
Предподсчет самых удаленных вершин можно сделать даже за O(N) обычным дфсом, хотя на том контесте я написал за квадрат и оно прошло. Предподсчет предков с расстояниями-степенями двойки можно сделать за O(NlogN). Отвечать на запрос можно за O(logN), поэтому суммарная сложность выходит O(NlogN+MlogN).
Спасибо огромное. Я знаю задачу на дереве нахождения 2 наиболее отдаленных вершины (диаметр). А вот как за одни проход найти для каждой вершины наиболее удаленного?
Нам нужно для всех вершин найти самые удаленные. Пусть мы ищем самую удаленную вершину(w) от v. Есть 2 варианта ее расположения относительно v:
1) w лежит в поддереве с корнем в v.
2) w не лежит в поддереве с корнем в v.
Для начала для каждой вершины v найдем самую удаленную вершину, лежащую в поддереве с корнем в v (назовем ее v_f). Это можно сделать одним дфсом. Так же для каждой вершины v запомним вторую по расстоянию вершину от нее, лежащую в поддереве с корнем в v (назовем ее v_s).
Теперь найдем для каждой вершины v самую удаленную вершину, не лежащую в поддереве с корнем в v (назовем ее v_k). Очевидно, что тогда w либо будет совпадать с v_f, либо с v_k (зависит от того, какая дальше). Запустим дфс от корня. Если мы стоим в вершине v, то будем хранить в стеке всех предков v, а так же самые удаленные вершины от них в поддеревьях с корнями в них, но не принадлежащие поддереву с корнем в v. Чтобы найти v_k, нам нужно выбрать вершину из стека, до которой расстояние от v - максимальное. В стеке можно сохранять еще и максимум, так что такая вершина находится за О(1). Теперь нам нужно рекурсивно перейти в потомков v. Если мы переходим в потомка, в поддереве с корнем в котором лежит v_f, то добавим в стек v_s, иначе добавим v_f. Учитывая, что от всех потомков идти до v на 1 ребро меньше чем до ее предка, а от предка идти на 1 ребро меньше чем до ее предка и т.д., добавим вершину не с настоящим расстоянием до нее, а с расстоянием уменьшенным на v_h (высота v). В таком случае мы не будем помнить реального максимального расстояния, но относительные расстояния сохранятся, так что зная самую удаленную вершину мы можем легко восстановить расстояние до нее.
делается двумя dfsами на первом считаешь самую удаленную в _текущем поддереве_
на втором в в параметры dfs а еще добавляешь самую удаленную вершину и путь до нее "снизу" текущего дерева
Спасибо огромное. Респект и уважуха Побольше бы таких людей как вы.
Попробовал реализовать это хитрое решение, оно естественно сработало, за что вам большое спасибо, было интересно.
Хорошая задача, содержит в себе много подзадач (нахождение самых удаленных вершин, вычисление 1-2-4-8-... предков, LCA, etc).
И вот у меня вопрос. Правильно ли я понял идею с вычислением предков? Сделано у меня так:
vector<vector<int> > deg2;
vector<int> st3;
void dfs3(int u)
{
t_verts& verts = G[u];
int h = height[u];
for(int i=1; h-i>=0; i<<=1)
deg2[u].push_back(st3[h-i]);
st3.push_back(u);
for_each(verts.begin(), verts.end(), [] (const int v) { dfs3(v); });
st3.pop_back();
}
// вычисление k-го предка для вершины u
int predcessor(int u, int k)
{
if(k<0 || k>height[u]) for(;;);
if(k==0) return u;
int t=k, x=0;
for(; t!=0; x++,t>>=1); x--;
int p = 1<<x;
return predcessor(deg2[u][x], k-p);
}
int main()
{
// ...
deg2.resize(n);
st3.reserve(maxheight+1);
dfs3(root);
st3.reserve(0);
// ...
}
Да, это похоже на правду. Только при такой реализации predcessor() выполняется за O(log^2(N)). Чтобы был просто логарифм нужно в начале еще предпосчитать для каждого числа от 1 до maxheight наибольшую степень двойки, не превышающую его.
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Problems » timus 1752