CF1805D A Wide, Wide Graph
  YdxfFsjpYokY 2023年11月02日 44 0


也许更好的阅读体验

CF1805D A Wide, Wide Graph_连通分量

给你一棵有 CF1805D A Wide, Wide Graph_连通分量_02 个结点的树,定义 CF1805D A Wide, Wide Graph_树的直径_03为将在原树中所有距离大于等于 CF1805D A Wide, Wide Graph_连通分量_04 的点对间连一条无向边所构成的无向图(距离定义为简单路径中边的数量)。

对于所有 CF1805D A Wide, Wide Graph_树的直径_05,求 CF1805D A Wide, Wide Graph_树的直径_03 中连通块的数量。

CF1805D A Wide, Wide Graph_c++_07

CF1805D A Wide, Wide Graph_算法_08

设树的直径为CF1805D A Wide, Wide Graph_树的直径_09,对于CF1805D A Wide, Wide Graph_树的直径_10的情况,CF1805D A Wide, Wide Graph_树的直径_03中没有边,连通块的数量为CF1805D A Wide, Wide Graph_连通分量_02

以下是我的思考过程,逐渐从比较麻烦的想法变得简单

可以先看正解,没看懂再回来看

考虑CF1805D A Wide, Wide Graph_连通分量_04从大变小的过程,之前连了的边CF1805D A Wide, Wide Graph_连通分量_04变小后也会连,因此可以考虑每次增加的新点

这时候想到了直径,假设整棵树只有一条直径,CF1805D A Wide, Wide Graph_acm_15时,只有直径的两个端点是连在一起的,考虑CF1805D A Wide, Wide Graph_连通分量_04变小的过程,因为任意一个点到其它点最远的距离就是到这条直径的某个端点,最开始两个端点连了边,当CF1805D A Wide, Wide Graph_连通分量_04变小CF1805D A Wide, Wide Graph_连通分量_18,可以认为从直径的一个端点出发最多走CF1805D A Wide, Wide Graph_连通分量_18步,所到达的这些点都会和直径的另一个端点连起来

如图,两个直径端点在CF1805D A Wide, Wide Graph_连通分量_04变小的过程会不断新增另一端点附近的点

CF1805D A Wide, Wide Graph_算法_21


这样的过程可以用CF1805D A Wide, Wide Graph_算法_22模拟出来,目前这种做法仍然有问题,一是树并不是只有一条直径,对于多条直径其实也可以用CF1805D A Wide, Wide Graph_算法_23找出来然后再CF1805D A Wide, Wide Graph_算法_22模拟,二是比较关键的问题,如下的情况并没有被正确考虑到

CF1805D A Wide, Wide Graph_c++_25


蓝色的点对于左端点而言要走三步下才能到达,而对右端点而言,它们的距离为CF1805D A Wide, Wide Graph_acm_26,应该早就被连边,而在我们的CF1805D A Wide, Wide Graph_算法_22模拟的方法中,并没能正确的连接到

以下是正解部分
现在让我们舍弃掉CF1805D A Wide, Wide Graph_算法_22这个愚蠢的方法,首先重新捋一下几个性质

  • 所有直径端点在CF1805D A Wide, Wide Graph_树的直径_29时都会连边进同一个连通分量
  • 除了和直径端点在同一个连通分量里的点,其它点都是独立的大小为1连通分量
  • 离直径端点距离为CF1805D A Wide, Wide Graph_连通分量_30的点,在CF1805D A Wide, Wide Graph_acm_31时会和直径端点连边

根据以上性质,我们可以发现我们需要求出的东西是,每个点到所有直径端点的距离中最远距离CF1805D A Wide, Wide Graph_树的直径_32,这个点会在CF1805D A Wide, Wide Graph_算法_33时,进入直径端点所在连通分量,也就是连通分量数会减少CF1805D A Wide, Wide Graph_算法_34,令CF1805D A Wide, Wide Graph_算法_35,也就是当CF1805D A Wide, Wide Graph_连通分量_04CF1805D A Wide, Wide Graph_树的直径_09开始减少CF1805D A Wide, Wide Graph_连通分量_18时联通分量数会减少CF1805D A Wide, Wide Graph_算法_34
现在问题就变成了有若干个点(直径端点),求每个点到这些点最远的距离
因为是直径端点,因此会有一些性质让问题变得好求,首先如果有多个直径,并且这些直径的端点没有相同的点时,这两些直径的交点一定是在距离某个直径端点CF1805D A Wide, Wide Graph_算法_40的位置
若直径为偶数,我们把这个树从直径中间的位置提起来

CF1805D A Wide, Wide Graph_连通分量_41

这时,这棵树的深度不会超过 CF1805D A Wide, Wide Graph_算法_40,任意一点都可越过根节点走到某一个直径端点,也就是说任意一点到某个直径端点的最长距离为 CF1805D A Wide, Wide Graph_连通分量_43,对应的 CF1805D A Wide, Wide Graph_c++_44
而对于直径为奇数的情况
我们也找到中间位置

CF1805D A Wide, Wide Graph_树的直径_45

先考虑右边这部分,将红色的点提出来作为根节点,这时只考虑右边这部分点,不考虑左边的点,这些点可以越过根节点然后走到某一个离红色点长度为 CF1805D A Wide, Wide Graph_树的直径_46的直径端点,也就是说最长距离为距离为 CF1805D A Wide, Wide Graph_c++_47,对应的 CF1805D A Wide, Wide Graph_c++_44
而对于左边这部分,我们只需把红色的点往左移一次,就能变成相同的情况了
我们发现直径为奇数和偶数的情况得到的 CF1805D A Wide, Wide Graph_连通分量_18的计算式子是一样的,因此可以共用同一个 CF1805D A Wide, Wide Graph_算法_23解决
现在只剩下一个简单的问题,如何找到直径的中点,这个问题应该有很多种解决办法,我是使用记录儿子中最深和次深的点是谁来求直径,并记录找到直径的结点,顺便用 CF1805D A Wide, Wide Graph_c++_51表示以 CF1805D A Wide, Wide Graph_连通分量_18为根节点的子树到最深的点应该往 CF1805D A Wide, Wide Graph_连通分量_18的哪个儿子走,这样只需从之前记录的结点开始每次都往 CF1805D A Wide, Wide Graph_c++_51的方向走,直到找到最深和次深的深度相同或者相差一就找到了一条直径的中点了
所有的点的 CF1805D A Wide, Wide Graph_连通分量_18都得到了,之后我们就可以直接计算在 CF1805D A Wide, Wide Graph_c++_56时会减少多少个连通分量了,问题就解决了

CF1805D A Wide, Wide Graph_acm_57

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 200005;
int n, cnt, d, g;
int head[maxn], nxt[maxn], to[maxn];
int mx1[maxn], mx2[maxn], dep[maxn], s1[maxn];
int ans[maxn], need[maxn];
queue <int> q;
void add (int u, int v)
{
    nxt[++cnt] = head[u], head[u] = cnt, to[cnt] = v;
}
void dfs1 (int u, int father)
{
    dep[u] = dep[father] + 1;
    mx1[u] = mx2[u] = u;
    for (int e = head[u]; e; e = nxt[e])
        if (to[e] != father) {
            dfs1(to[e], u);
            if (dep[mx1[to[e]]] > dep[mx2[u]])    mx2[u] = mx1[to[e]];
            if (dep[mx2[u]] > dep[mx1[u]])    swap(mx1[u], mx2[u]);
            if (mx1[to[e]] == mx1[u])   s1[u] = to[e];
        }
    int dis = dep[mx1[u]] + dep[mx2[u]] - 2 * dep[u];
    if (dis > d) {
        d = dis;
        g = u;
    }
}
void dfs2 (int u, int father)
{
    dep[u] = dep[father] + 1;
    need[u] = min(need[u], d / 2 - (dep[u] - 1));
    for (int e = head[u]; e; e = nxt[e])
        if (to[e] != father) dfs2(to[e], u);
}
int main ()
{
    scanf("%d", &n);
    for (int i = 2, u, v; i <= n; ++i) {
        scanf("%d%d", &u, &v);
        add(u, v), add(v, u);
    }
    for (int i = 1; i <= n; ++i)    need[i] = n;
    dfs1(1, 0);
    for (int i = n; i > d; --i) ans[i] = n;
    if (d & 1) {
        while (dep[mx1[g]] - dep[g] != d / 2 + 1)   g = s1[g];
        dep[s1[g]] = 0;
        dfs2(g, s1[g]);
        dep[g] = 0;
        dfs2(s1[g], g);
    }
    else {
        while (dep[mx1[g]] - dep[g] != d / 2)   g = s1[g];
        dfs2(g, 0);
    }
    for (int i = 1; i <= n; ++i)    --ans[d - need[i]];
    ++ans[d];
    for (int i = d; i; --i) ans[i] += ans[i + 1];
    for (int i = 1; i <= n; ++i)    printf("%d%c", ans[i], " \n"[i == n]);
    return 0;
}

如有哪里讲得不是很明白或是有错误,欢迎指正
如您喜欢的话不妨点个赞收藏一下吧


【版权声明】本文内容来自摩杜云社区用户原创、第三方投稿、转载,内容版权归原作者所有。本网站的目的在于传递更多信息,不拥有版权,亦不承担相应法律责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@moduyun.com

上一篇: [SCOI2015] 国旗计划 下一篇: CF1839D Ball Sorting
  1. 分享:
最后一次编辑于 2023年11月08日 0

暂无评论

推荐阅读
YdxfFsjpYokY