CodeForces 455C

谁借莪１个温暖的怀抱￠ 2021-10-18 08:38 241阅读 0赞

## 题意：给定N，M和Q，N表示有N个城市，M条已经修好的路，修好的路是不能改变的，然后是Q次操作，操作分为两种，一种是查询城市x所在的联通集合中，最长的路为多长。二是连接两个联通集合，采用联通之后最长路最短的方案。 ##

## 分析：两树合并时，设直径分别为len1，len2，新树直径为max(len1,len2,(len1/2)+(len2/2)+(len1%2)+(len2%2)+1)，即两颗旧树的直径，两颗旧树直径的一半向上取整加一，中的较大值。注意并查集要压缩路径，启发式合并也可以有效降低复杂度。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    const int N = 1e6+5;
    int n,m,q,p[N],s[N],d[N],dd[N],td,pt;
    vector<int> g[N];
    
    int fd(int x) {
        return p[x] == x ? x : p[x] = fd(p[x]);
    }
    
    void dfs1(int x,int v) {
        d[x]=v;
        if(d[x]>td) {
            td=v;
            pt=x;
        }
        for(int i=0;i<g[x].size();i++) {
            int u=g[x][i];
            if(!d[u]) dfs1(u,v+1);
        }
    }
    
    void dfs2(int x,int v) {
        dd[x]=v;
        if(dd[x]>td) td=dd[x];
        for(int i=0;i<g[x].size();i++) {
            int u=g[x][i];
            if(!dd[u]) dfs2(u,v+1);
        }
    }
    
    int main() {
        scanf("%d%d%d",&n,&m,&q);
        for(int i=1;i<=n;i++) p[i]=i;
        for(int i=1;i<=m;i++) {
            int a,b;
            scanf("%d%d",&a,&b);
            g[a].push_back(b);
            g[b].push_back(a);
            int x=fd(a),y=fd(b);
            if(x!=y) p[x]=y;
        }
        for(int i=1;i<=n;i++) {
            if(!d[i]) {
                pt=i;
                td=0;
                dfs1(i,1);
                td=0;
                dfs2(pt,1);
                int fa=fd(pt);
                s[fa]=td-1;
            }
        }
        for(int i=1;i<=q;i++) {
            int op,a,b;
            scanf("%d",&op);
            if(op==1) {
                scanf("%d",&a);
                printf("%d\n",s[fd(a)]);
            }
            else {
                scanf("%d%d",&a,&b);
                int x=fd(a),y=fd(b);
                if(x==y) continue;
                p[x]=y;
                s[y]=max(s[x],max(s[y],(1+s[x])/2+(1+s[y])/2+1));
            }
        }
        return 0;
    }