CF455C Civilization

题解 数据结构-并查集 图论-树的直径 省选/NOI-
题目链接 编辑文章

双倍经验:洛谷2195 HXY造公园

题意

给出一个有 $n(\le 3\times 10^5)$ 个点 $m(\le 3\times 10^5)$ 条边的森林。要求支持两种操作:

  1. 求 $x$ 所在树的直径
  2. 将 $x,y$ 所在的树合并,要求合并后树的直径最小

题解

合并可以用并查集来实现,用 $ans[x]$ 表示 $x$ 子树中的直径长度。

对于操作 $1$ ,直接输出 $ans[x]$ 。

对于操作 $2$ ,合并后的直径是以下两种情况的较大值:

  1. 还是原来某棵树的直径
  2. 有两棵树的直径组成

对于情况 $2$ ,将两棵树直径的中心连起来一定是最优的,这时的新直径长度为 $\lceil \frac{ans[x]}{2}\rceil + \lceil \frac{ans[y]}{2}\rceil+1$ 。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const int N=300005;
struct Edge {
    int next,to;
} edge[N<<1];
bool vis[N];
int cnt,head[N],n,m,q,a,b,c,fa[N],mx,mxi,ans[N];

inline void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

inline void init() { for (int i=1;i<=n;i++) fa[i]=i; }

int getfa(int x) { return x==fa[x] ? x : fa[x]=getfa(fa[x]); }

inline bool merge(int x,int y)
{
    int gfx=getfa(x),gfy=getfa(y);
    if (gfx==gfy) return 0;
    return fa[gfx]=gfy,1;
}

void dfs(int x,int f,int dep)
{
    vis[x]=1;
    if (dep>mx) mx=dep,mxi=x;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (y==f) continue;
        dfs(y,x,dep+1);
    }
}

signed main()
{
    n=read(); m=read(); q=read();
    init();
    for (int i=1;i<=m;i++)
    {
        a=read(); b=read();
        add(a,b);
        add(b,a);
        merge(a,b);
    }
    for (int i=1;i<=n;i++)
    {
        if (vis[i]) continue;
        mx=0; mxi=i;
        dfs(i,0,0);
        int rt=mxi; mx=0;
        dfs(rt,0,0);
        ans[getfa(i)]=mx; //得到 i 所在树的直径
    }
    while (q--)
    {
        a=read(); b=read();
        if (a==1) printf("%d\n",ans[getfa(b)]);
        else
        {
            c=read();
            int x=getfa(b),y=getfa(c);
            if (x==y) continue;
            fa[x]=y; //合并
            ans[y]=max((ans[x]+1)/2+(ans[y]+1)/2+1,max(ans[x],ans[y])); //新直径
        }
    }
    return 0;
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空