Тема: timus 1752
Здравствуйте!
http://acm.timus.ru/problem.aspx?space=1&num=1752
Собственно сабж. Вообще не представляю как решить за разумное время (естественно не перебор)...
2 2010-06-02 16:44:29 Отредактировано KADR (2010-06-02 16:50:26)
Re: timus 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).
Re: timus 1752
Спасибо огромное. Я знаю задачу на дереве нахождения 2 наиболее отдаленных вершины (диаметр). А вот как за одни проход найти для каждой вершины наиболее удаленного?
Re: timus 1752
Нам нужно для всех вершин найти самые удаленные. Пусть мы ищем самую удаленную вершину(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). В таком случае мы не будем помнить реального максимального расстояния, но относительные расстояния сохранятся, так что зная самую удаленную вершину мы можем легко восстановить расстояние до нее.
5 2010-06-03 17:06:18 Отредактировано Oleg (2010-06-03 21:58:42)
Re: timus 1752
делается двумя dfsами на первом считаешь самую удаленную в _текущем поддереве_
на втором в в параметры dfs а еще добавляешь самую удаленную вершину и путь до нее "снизу" текущего дерева
Re: timus 1752
Спасибо огромное. Респект и уважуха 
Побольше бы таких людей как вы.
Re: timus 1752
Попробовал реализовать это хитрое решение, оно естественно сработало, за что вам большое спасибо, было интересно.
Хорошая задача, содержит в себе много подзадач (нахождение самых удаленных вершин, вычисление 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);
// ...
}8 2011-03-12 01:15:44 Отредактировано KADR (2011-03-12 01:16:20)
Re: timus 1752
Да, это похоже на правду. Только при такой реализации predcessor() выполняется за O(log^2(N)). Чтобы был просто логарифм нужно в начале еще предпосчитать для каждого числа от 1 до maxheight наибольшую степень двойки, не превышающую его.