Codeforces Round 769 (Div. 2) |
---|
Закончено |
Эта версия задачи отличается от предыдущей только ограничением на $$$n$$$.
Дерево — это связный неориентированный граф без циклов. Взвешенное дерево — это такое дерево, в котором у каждого ребра есть некоторый вес. Расстояние между вершинами — минимальная сумма весов на пути между ними.
Дано взвешенное дерево c $$$n$$$ вершинами, у каждого ребра вес $$$1$$$. Введём $$$d(v)$$$ как расстояние между вершиной $$$1$$$ и вершиной $$$v$$$.
Пусть $$$f(x)$$$ равно минимально возможному значению $$$\max\limits_{1 \leq v \leq n} \ {d(v)}$$$, если можно временно добавить одно ребро веса $$$x$$$ между любыми двумя вершинами $$$a$$$ и $$$b$$$ $$$(1 \le a, b \le n)$$$. Обратите внимание, что после этой операции граф уже не является деревом.
Для каждого целого числа $$$x$$$ от $$$1$$$ до $$$n$$$ найдите $$$f(x)$$$.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$)
Каждая из следующих $$$n−1$$$ строк содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u,v \le n$$$), указывающих на наличие ребра между вершинами $$$u$$$ и $$$v$$$. Гарантируется, что заданные ребра образуют дерево.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$3 \cdot 10^5$$$.
Для каждого набора входных данных выведите в одной строке $$$n$$$ целых чисел, $$$x$$$-е из которых равно $$$f(x)$$$ для всех $$$x$$$ от $$$1$$$ до $$$n$$$.
341 22 31 421 271 21 33 43 53 65 7
1 2 2 2 1 1 2 2 3 3 3 3 3
Название |
---|