D. A Wide, Wide Graph
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$.
Input
The 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.
Output
Output $n$ integers: the number of connected components in the graph $G_k$ for each $k$ from $1$ to $n$.
Examples
input
6 1 2 1 3 2 4 2 5 3 6
output
1 1 2 4 6 6
input
5 1 2 2 3 3 4 3 5
output
1 1 3 5 5
Note
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.
解题思路
容易发现当$k = 1$时,$G_1$必然只有一个连通块。当$k = n$时,$G_n$有$n$个连通块,即不存在任何一条边,这是因为树中任意两点距离不超过$n-1$。可以发现随着$k$的增大$G_k$中连通块的数量会逐渐增加,即$G_k$中的边会逐渐减少。因此我们可以从大到小枚举$k$,这就等价于每次在$G_k$中加边,然后求有多少个连通块,这就比删边好处理了。
我们知道树中最长的路径为树的直径,假设直径长度为$d$,因此如果$k > d$,那么$G_k$中必然不存在任何一条边,而当$k=d$,此时$G_k$中所有直径的端点构成一个连通块。而除了端点(端点指直径的端点,下同)之外,其他的点只有在$k < d$时才能被连边。那么对于某个点$v$,$k$枚举到多少才能与其他的点连一条边呢?假设从点$v$出发最远能走到点$w$(此时$w$必然是一个端点,证明参考此处链接),路径长度为$d_{vw}$,那么当$k = d_{vw}$时$v$和$w$连一条边。因此对于某个点$v$,只有当$k$至少枚举(从大到小枚举)到$v$能走到的最远距离时,$v$才能被连一条边加入到某个连通块中。
然后这里有个性质,假设$v$最远能走到的点构成的点集$S$,那么任意一条直径的两个端点$x$和$y$,必然满足$x \in S$或$y \in S$(也可能同时满足)。下面来证明这个性质,证明方法与链接证明树的直径的方法相似。
假设树的直径的两个端点为$x$和$y$,求$v$最远能走到的点,分情况讨论:
情况$1$:$v$是直径上点。反证法$v$最远能走到的点为$w$($w$必然不在直径上)而不是$x$和$y$。
那么有$d_{vw} > d_{vx}$,$d_{vw} > d_{vy}$。从而有$d_{vx} + d_{vw} > d_{vx} + d_{vy}$,即$x \to v \to w$是一条更长的直径,这就与端点$xy$所构成的路径是直径矛盾了。
情况$2$:$v$不是直径上点。反证法$v$最远能走到的点为$w$而不是$x$和$y$。
那么有$d_{vw} > d_{vu} + d_{ux}$,$d_{vw} > d_{vu} + d_{uy}$。由于$d_{vu} > 0$,从而有$d_{vw} + d_{vu} > d_{vu} + d_{uy}$,从而有$d_{vw} + d_{vu} > d_{uy}$,有$d_{ux} + d_{vw} + d_{vu} > d_{ux} + d_{uy}$。即$x \to u \to v \to w$是一条更长的直径,这就与端点$xy$所构成的路径是直径矛盾了。
有了这个性质后,当$k$枚举到$v$能走到的最远距离时,在$G_k$中$v$必然至少会与端点$x$和$y$中的一个连一条边。又因为$x$和$y$已经在一个连通中,因此$v$必然会在端点所在的连通块中。即当$k$枚举到$v$能走到的最远距离时,$v$必然会在端点所在的连通块。
因此我们可以先通过两遍$\text{dfs}$找到任意一条直径的两个端点$x$和$y$,然后分别求其余点到$x$和$y$的最远距离,也就是从其余点出发能走到的最长距离。然后从大到小枚举$k$,在这个过程中把所有最长距离为$k$的点都加入到端点所在的连通块中,由于一开始每一个点都是一个连通块,这就等价于连通块数量减$1$。
AC代码如下:
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int N = 1e5 + 10, M = N * 2; 5 6 int head[N], e[M], ne[M], idx; 7 int d1[N], d2[N]; 8 int ans[N]; 9 10 void add(int v, int w) { 11 e[idx] = w, ne[idx] = head[v], head[v] = idx++; 12 } 13 14 void dfs(int u, int pre, int *d) { 15 for (int i = head[u]; i != -1; i = ne[i]) { 16 if (e[i] != pre) { 17 d[e[i]] = d[u] + 1; 18 dfs(e[i], u, d); 19 } 20 } 21 } 22 23 int main() { 24 int n; 25 scanf("%d", &n); 26 memset(head, -1, sizeof(head)); 27 for (int i = 0; i < n - 1; i++) { 28 int v, w; 29 scanf("%d %d", &v, &w); 30 add(v, w), add(w, v); 31 } 32 dfs(1, -1, d1); 33 int x = max_element(d1 + 1, d1 + n + 1) - d1; // 找到其中一个端点x 34 d1[x] = 0; 35 dfs(x, -1, d1); // 找到另外一个端点y,同时求x到其他点的距离 36 int y = max_element(d1 + 1, d1 + n + 1) - d1; 37 dfs(y, -1, d2); // 求y到其他点的距离 38 for (int i = 1; i <= n; i++) { 39 d1[i] = max(d1[i], d2[i]); // 求每个点到端点x和y的最长距离 40 } 41 sort(d1 + 1, d1 + n + 1); 42 ans[n] = n; // k=n必然有n个连通块 43 for (int i = n - 1, j = n - 1; i; i--) { // 从大到小枚举k 44 ans[i] = ans[i + 1]; 45 while (j && d1[j] == i) { // 把所有最长距离为k的点找出来 46 j--; 47 ans[i]--; // 连通块数量减1 48 } 49 } 50 for (int i = 1; i <= n; i++) { 51 printf("%d ", ans[i]); 52 } 53 54 return 0; 55 }
参考资料
Editorial of Codeforces Round #862 (Div. 2):https://codeforces.com/blog/entry/114644
Codeforces Round 862 (Div. 2) D~E:https://zhuanlan.zhihu.com/p/619152050
Codeforces Round 862 (Div. 2) A - D:https://zhuanlan.zhihu.com/p/618971125
标签:Wide,连通,int,graph,vw,端点,Graph,d1 From: https://www.cnblogs.com/onlyblues/p/17285180.html