D55 树的直径 树形DP+并查集 P2195 HXY造公园

// 树的直径 树形DP+并查集 O(n)
#include<bits/stdc++.h>
using namespace std;

const int N=300010;
int n,m,q;
int fa[N],d[N],len,zj[N];
vector<int> e[N];

int find(int x){
  return fa[x]==x?x:fa[x]=find(fa[x]);
}
void dfs(int x,int f){ //树形DP 
  for(auto y:e[x])if(y!=f){
    dfs(y,x);
    len=max(len,d[x]+1+d[y]); //保存直径
    d[x]=max(d[x],d[y]+1);    //x子树的最长链
  }
}
int main(){
  scanf("%d%d%d",&n,&m,&q);
  for(int i=1;i<=n;++i) fa[i]=i;
  for(int i=1,x,y;i<=m;++i){
    scanf("%d%d",&x,&y);
    e[x].push_back(y);
    e[y].push_back(x);
    fa[find(x)]=find(y);
  }
  for(int i=1;i<=n;++i)if(fa[i]==i){ //i是树根
    len=0;
    dfs(i,0);
    zj[i]=len; //每颗树的直径存在根上
  }
  for(int i=1,opt,x,y;i<=q;++i){
    scanf("%d%d",&opt,&x);
    if(opt==1) printf("%d\n",zj[find(x)]);
    else{
      scanf("%d",&y);
      x=find(x),y=find(y);
      if(x!=y){
        fa[x]=y; //合并集合
        zj[y]=max(((zj[x]+1)>>1)+((zj[y]+1)>>1)+1,max(zj[x],zj[y]));
        //新直径=max{(两个半径之和+1,1是连接边),x的直径,y的直径}
      }
    }
  }
}