310253: CF1805D. A Wide, Wide Graph
Description
You are given a tree (a connected graph without cycles) with $n$ vertices.
Consider a fixed integer $k$. Then, the graph $G_k$ is an undirected graph with $n$ vertices, where an edge between vertices $u$ and $v$ exists if and only if the distance between vertices $u$ and $v$ in the given tree is at least $k$.
For each $k$ from $1$ to $n$, print the number of connected components in the graph $G_k$.
InputThe first line contains the integer $n$ ($2 \le n \le 10^5$) — the number of vertices in the graph.
Each of the next $n-1$ lines contains two integers $u$ and $v$ ($1 \le u, v \le n$), denoting an edge between vertices $u$ and $v$ in the tree. It is guaranteed that these edges form a valid tree.
OutputOutput $n$ integers: the number of connected components in the graph $G_k$ for each $k$ from $1$ to $n$.
ExamplesInput6 1 2 1 3 2 4 2 5 3 6Output
1 1 2 4 6 6Input
5 1 2 2 3 3 4 3 5Output
1 1 3 5 5Note
In the first example: If $k=1$, the graph has an edge between each pair of vertices, so it has one component. If $k=4$, the graph has only edges $4 \leftrightarrow 6$ and $5 \leftrightarrow 6$, so the graph has $4$ components.
In the second example: when $k=1$ or $k=2$ the graph has one component. When $k=3$ the graph $G_k$ splits into $3$ components: one component has vertices $1$, $4$ and $5$, and two more components contain one vertex each. When $k=4$ or $k=5$ each vertex is a separate component.
Input
题意翻译
给定一棵 $n$（$2\leq n\leq 10^5$）个节点的无根树，对于每个 $k$（$1\leq k \leq n$），定义一个无向图 $G_k$，其中由边连接的两个节点 $u$ 和 $v$ 的距离至少为 $k$。请你计算 $G_k$ 的连通块个数。 ## 输入格式 第一行包含整数 $n$。 接下来 $n-1$ 行，每行包含两个整数 $u$ 和 $v$，表示树上的一条无向边。 ## 输出格式 输出共 $n$ 行，每行一个整数，表示 $G_k$ 的连通块个数。 ## 数据范围 $2\leq n\leq 10^5$ ## 提示 第一个样例中，当$k=1$时，所有的点都连通；当$k=4$时，只有$(4,6)$和$(5,6)$两条边连通，所以连通块个数为4。 第二个样例中，当$k=3$时，节点1、4、5构成一个连通块，其余两个节点分别为一个连通块。Output
你给定一个有n个顶点的树（一个没有环的连通图）。考虑一个固定的整数k。然后，图Gk是一个有n个顶点的无向图，如果且仅如果在给定树中顶点u和v之间的距离至少为k，则在顶点u和v之间存在一条边。对于每个k从1到n，打印图Gk中的连通分量数。
输入数据格式：
第一行包含整数n（2≤n≤10^5）——图中顶点的数量。
接下来n-1行，每行包含两个整数u和v（1≤u，v≤n），表示树中顶点u和v之间的边。保证这些边形成一个有效的树。
输出数据格式：
输出n个整数：对于每个k从1到n，图Gk中的连通分量数。
示例：
输入：
6
1 2
1 3
2 4
2 5
3 6
输出：
1 1 2 4 6 6
注意：
在第一个例子中：如果k=1，则图中每对顶点之间都有一条边，所以它只有一个分量。如果k=4，则图中只有边4↔6和5↔6，所以图有4个分量。
在第二个例子中：当k=1或k=2时，图只有一个分量。当k=3时，图Gk分裂为3个分量：一个分量包含顶点1、4和5，另外两个分量各包含一个顶点。当k=4或k=5时，每个顶点都是一个独立的分量。题目大意： 你给定一个有n个顶点的树（一个没有环的连通图）。考虑一个固定的整数k。然后，图Gk是一个有n个顶点的无向图，如果且仅如果在给定树中顶点u和v之间的距离至少为k，则在顶点u和v之间存在一条边。对于每个k从1到n，打印图Gk中的连通分量数。 输入数据格式： 第一行包含整数n（2≤n≤10^5）——图中顶点的数量。 接下来n-1行，每行包含两个整数u和v（1≤u，v≤n），表示树中顶点u和v之间的边。保证这些边形成一个有效的树。 输出数据格式： 输出n个整数：对于每个k从1到n，图Gk中的连通分量数。 示例： 输入： 6 1 2 1 3 2 4 2 5 3 6 输出： 1 1 2 4 6 6 注意： 在第一个例子中：如果k=1，则图中每对顶点之间都有一条边，所以它只有一个分量。如果k=4，则图中只有边4↔6和5↔6，所以图有4个分量。 在第二个例子中：当k=1或k=2时，图只有一个分量。当k=3时，图Gk分裂为3个分量：一个分量包含顶点1、4和5，另外两个分量各包含一个顶点。当k=4或k=5时，每个顶点都是一个独立的分量。