20分求助
  • 板块P2195 HXY造公园
  • 楼主Yuuu7
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/3/17 01:02
  • 上次更新2023/10/23 21:22:01
查看原帖
20分求助
646364
Yuuu7楼主2023/3/17 01:02
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 3e5+10;
vector <int > g[maxn];
int n,m,q;
int d[maxn];
int dis[maxn];
int fa[maxn];
int vis[maxn];
int c;
int find(int x)
{
    return fa[x]==x?fa[x]:fa[x]=find(fa[x]);
}
void merge(int x,int y)
{
    int fx=find(x);
    int fy=find(y);
    if(fx==fy) return ;
    fa[fx]=fy;
}
void dfs(int u,int f)
{
    for(auto v:g[u])
    {
        if(v==f) continue;
        d[v]=d[u]+1;
        if(d[v]>d[c]) c=v;
        dfs(v,u);
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>m>>q;
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
        merge(x,y);
    }
    for(int i=1;i<=n;i++)
    {
        if(fa[i]!=i) continue;
        int x=find(i);
        d[x]=0;dfs(x,-1);
        d[c]=0;dfs(c,-1);
        dis[x]=d[c];
    }
    while(q--)
    {
        int op;
        cin>>op;
        if(op==1)
        {
            int x;
            cin>>x;
            cout<<dis[find(x)]<<endl;
        }
        else
        {
            int x,y;
            cin>>x>>y;
            int fx=find(x);
            int fy=find(y);
            if(fx==fy) continue;
            dis[fy]=max(max((dis[fx]+1)/2+(dis[fy]+1)/2+1,dis[fy]),dis[fx]);
            merge(x,y);
        }
    }
    return 0;
}
2023/3/17 01:02
加载中...