Задача №114564. Древесные жабы (и лягушки)
Древесные жабы живут на деревьях. Как известно, дерево — это связный граф, такой, что между любыми двумя вершинами существует ровно один простой путь. Более строго, дерево состоит из вершин и соединяющих пары вершин рёбер. Из каждой вершины переходя по рёбрам можно добраться до любой другой вершины, при этом, если не переходить по одному ребру несколько раз, то путь из одной вершины в другую будет единственным. Можно показать, что в таких графах ровно \(n-1\) ребро, где \(n\) — число вершин в графе.
Так вот, задача вообще-то про жаб. В каждой из вершин сидит по жабе. Первая жаба сидит в вершине с номером \(1\), вторая жаба — в вершине с номером \(2\) и так далее. За одну единицу времени каждая из жаб может перейти по ребру в соседнюю вершину.
Жабы часто завидует другим жабам из-за того, что у них мало букашек.
Жабы успокаивают себя мыслью о том, что хоть у них букашек меньше, но они всё равно достаточно крутые жабы. Крутостью жабы назовём сумму номеров всех вершин, до каждой из которых в отдельности эта жаба может добраться строго быстрее первой жабы, если они начнут свой путь в одно и то же время.
Вас, как эксперта по жабам (и лягушкам), просят ответить на \(m\) запросов о крутости той или иной жабы, а именно, на каждый из \(m\) запросов, который задаётся одним числом \(u\), вам необходимо сообщить крутость \(u\)-й жабы.
В первой строке входного файла через пробел вводятся два числа \(n\) (\(1\le n\le 100\,000\)) — количество вершин в дереве и \(m\) (\(1\le m\le 100\,000\)) — количество запросов.
В следующих \(n-1\) строках описаны рёбра. Ребро задаётся числами \(x_i\) и \(y_i\) — номерами вершин, которые оно соединяет (\(1\le x_i,y_i \le n\), \(x_i \neq y_i\)). Гарантируется, что между любыми двумя вершинами существует единственный путь.
В следующих \(m\) строках описаны запросы. В \(i\)-й из них задано число \(u_i\) — номер очередной жабы, для которой надо определить её крутость. Вершины (и жабы) нумеруются с единицы.
На каждый из запросов \(u_i\) выведите по одному числу в отдельной строке — крутость жабы, сидящей в вершине \(u_i\).
В примере из условия ответ на первый запрос — \(27\), так как жаба, сидящая в вершине \(2\) может быстрее жабы номер \(1\) добратьcя до вершин \(2\), \(3\), \(4\), \(5\), \(6\), \(7\), то есть \(27\) в сумме.
Ответ на второй запрос — \(25\), так как жаба, сидящая в вершине \(4\) может быстрее жабы номер \(1\) добратьcя до вершин \(3\), \(5\), \(6\), \(7\).
Ответ на третий запрос — \(18\), так как жаба, сидящая в вершине \(7\) может быстрее жабы номер \(1\) добратьcя до вершин \(5\), \(6\), \(7\) (до вершин \(3\) и \(4\) они доберутся за одно и то же время).
Ответ на последний запрос — \(0\), так как жаба, сидящая в вершине \(1\) не сможет добраться ни до одной вершины быстрее, чем другая жаба, сидящая в вершине \(1\).
В данной задаче \(50\) тестов, помимо тестов из условия, каждый из них оценивается в \(2\) балла. Результаты работы ваших решений на первых \(35\) тестах будут доступны во время соревнования. Результаты работы на остальных \(15\) будут доступны после окончания соревнования.
Решения, корректно работающие при \(n, m \leq 100\), будут набирать не менее \(20\) баллов.
Решения, корректно работающие при \(n, m \leq 1000\), будут набирать не менее \(50\) баллов.
Решения, корректно работающие на графах, в которых из вершины не может исходить больше \(2\) рёбер, будут набирать не менее \(10\) баллов.
Решения, корректно работающие на тестах, в которых расстояние от каждой из вершин \(u_i\) до вершины 1 не превосходит \(20\), будут набирать не менее \(10\) баллов.
7 5 1 2 2 3 3 4 3 5 5 6 5 7 2 4 7 3 1
27 25 18 25 0