Hi guys.
I am trying to solve the following problem :
Given a tree, you must remove an edge and add an edge so that the new tree is connected and diameter of the new tree is smallest possible. Number of vertices are up to 300000.
When I remove any edge (u,v) I got 2 new trees: one rooted at v and one for which u is leaf. It is obvious that smallest diameter I can achieve is max{d(first tree),d(second tree),d(firs_tree)/2+d(second_tree)/2+1}. Now I can traverse over all edges and remove them and take minimum of those values. Now problem is: I can calculate the diameter of the hanging tree just using dynamic programming on the tree, but I am somehow in trouble of calculating the diameter of the trimmed tree. It seems it is also possible to calculate the diameter of the trimmed tree using dynamic programming but in opposite order, I mean from leaves to root or somehow, but I don't know how exactly to do that. Can anyone help me or give me some hints ?
Thanks in advance.

P.S. Problem is not from currently running contest.

Здравствуйте. Может кто знает как можно посчитать функцию Ейлера для всех i, 1 <= i <= n за время O(n)?

Всегда писал Миллера-Рабина для чисел в пределах [1, 2 ^ 31 - 1]. И вчера на одном OJ попалась задача,где нужно писать вышеупомянутый тест на простоту для чисел [1, 2 ^ 63 - 1].Все отлично, но вот возводить в степень за log(n) не получается.При возведении промежуточные результаты выходят за пределы long long.Не подскажите ли, знающие люди, как ето можно сделать ?

Кто нибудь может дать ссылку на задачи ACM-ICPC 2011-2012,NEERC Moscow Subregional Programming Contest 2011 ?

Если кто-нибудь может дать полезную ссылку на описание алгоритма  meet-in-the-middle или же сможет написать, что это за алгоритм буду признателен. Заранее спасибо.