CF1632E2.Distance Tree (hard version)

This version of the problem differs from the previous one only in the constraint on $n$.

A tree is a connected undirected graph without cycles. A weighted tree has a weight assigned to each edge. The distance between two vertices is the minimum sum of weights on the path connecting them.

You are given a weighted tree with $n$ vertices, each edge has a weight of $1$. Denote $d(v)$ as the distance between vertex $1$ and vertex $v$.

Let $f(x)$ be the minimum possible value of $\max\limits_{1 \leq v \leq n} \ {d(v)}$ if you can temporarily add an edge with weight $x$ between any two vertices $a$ and $b$ $(1 \le a, b \le n)$. Note that after this operation, the graph is no longer a tree.

For each integer $x$ from $1$ to $n$, find $f(x)$.

本题与前一版本的唯一区别在于对 $n$ 的约束条件。

树是一种无环的连通无向图。带权树为每条边赋予一个权重。两点之间的距离定义为连接它们的路径上边权之和的最小值。

给定一棵含 $n$ 个顶点的带权树，其中每条边的权重均为 $1$。记 $d(v)$ 为顶点 $1$ 与顶点 $v$ 之间的距离。

定义 $f(x)$ 为：在任意两个顶点 $a$ 和 $b$（$1 \le a, b \le n$）之间临时添加一条权重为 $x$ 的边后，$\max\limits_{1 \leq v \leq n} \ {d(v)}$ 所能取到的最小可能值。注意，执行此操作后，图将不再是一棵树。

对每个从 $1$ 到 $n$ 的整数 $x$，求出 $f(x)$。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($2 \le n \le 3 \cdot 10^5$).

Each of the next $n−1$ lines contains two integers $u$ and $v$ ($1 \le u,v \le n$) indicating that there is an edge between vertices $u$ and $v$. It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $3 \cdot 10^5$.

第一行包含一个整数 $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$。

For each test case, print $n$ integers in a single line, $x$-th of which is equal to $f(x)$ for all $x$ from $1$ to $n$.

对于每个测试用例，在一行中输出 $n$ 个整数，其中第 $x$ 个整数等于 $f(x)$（$x$ 从 $1$ 到 $n$）。

In the first testcase:

• For $x = 1$, we can an edge between vertices $1$ and $3$, then $d(1) = 0$ and $d(2) = d(3) = d(4) = 1$, so $f(1) = 1$.
• For $x \ge 2$, no matter which edge we add, $d(1) = 0$, $d(2) = d(4) = 1$ and $d(3) = 2$, so $f(x) = 2$.

在第一个测试用例中：

• 当 $x = 1$ 时，我们可以在顶点 $1$ 和 $3$ 之间添加一条边，此时 $d(1) = 0$，而 $d(2) = d(3) = d(4) = 1$，因此 $f(1) = 1$。
• 当 $x \ge 2$ 时，无论添加哪条边，均有 $d(1) = 0$，$d(2) = d(4) = 1$，且 $d(3) = 2$，因此 $f(x) = 2$。