首页 > 其他分享 >D. A Wide, Wide Graph

D. A Wide, Wide Graph

时间:2023-04-04 09:45:25浏览次数:53  
标签:Wide 连通 int graph vw 端点 Graph d1

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

相关文章