题解归档 - cf455C

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf455C
• 本地来源：problems/cf455C/idea.md
• 题目链接：https://codeforces.com/contest/455/problem/C
• 原始标题：CF455C Civilization

思路

CF455C Civilization

题意

$n$ 个点、初始 $m$ 条边构成森林。$q$ 次操作：

1. 1 x：输出 $x$ 所在连通块树的直径（最长简单路径边数）。
2. 2 x y：合并 $x,y$ 所在连通块，在两块各选一个点连边，使新树直径尽量小（并列任选）。

$n,q \le 3\cdot 10^5$。

思路

初始森林

仅对当前边集 BFS 找连通块，对每个块：

• 两次 BFS 求真实直径 $d$；
• 记录 up = (d+1)/2（到「中心」的最远距离，即半径上界）；
• 块内所有点 fa 指向该块代表根，根上存 diam、up。

合并（并查集）

若 find(x)==find(y) 跳过。否则设两树根直径 $d_x,d_y$，半径 $u_x,u_y=(d+1)/2$：

$$\text{newD}=\max\bigl(d_x,\ d_y,\ u_x+u_y+1\bigr)$$

新块 up=(newD+1)/2。这是把两棵树中心相连使最长路径最小的经典结论。

查询

输出 diam[find(x)]。

实现要点

• 初始边只用于建邻接表 + 分块算直径；在线合并不再改邻接表，只靠 DSU 维护 $(d,up)$。
• 两次 BFS 时 far 必须取当前最远点，不能取 BFS 队尾。
• 变量：fa,diam,up，队列 q2（避免与读入的 $q$ 冲突）。

验证

• 样例输出 4。
• 本地 brute（$n\le 5$ 暴搜最优连边）对拍 500 组通过（Kali 不可达时本机对拍）。

复杂度

初始化 $O(n+m)$，每次操作 $O(\alpha(n))$。

代码

来源：problems/cf455C/solution.cpp

/* Author: likely
 * Time: 2026-06-08 04:33:51
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=3e5;
vector<ll>ss[maxn+5],nodes;
ll fa[maxn+5],diam[maxn+5],up[maxn+5],vis[maxn+5],dist[maxn+5];
ll n,m,q,i,j,k,zc,a,b,u,v,far,pd;
queue<ll>q2;
ll findf(ll x){
    if(fa[x]!=x) fa[x]=findf(fa[x]);
    return fa[x];
}
ll bfs_far(ll s){
    while(!q2.empty()) q2.pop();
    for(j=1;j<=n;j++) dist[j]=-1;
    q2.push(s),dist[s]=0,far=s;
    while(!q2.empty()){
        u=q2.front(),q2.pop();
        for(j=0;j<(ll)ss[u].size();j++){
            v=ss[u][j];
            if(dist[v]==-1){
                dist[v]=dist[u]+1,q2.push(v);
                if(dist[v]>dist[far]) far=v;
            }
        }
    }
    return far;
}
ll tree_diam(){
    if((ll)nodes.size()<=1) return 0;
    far=bfs_far(nodes[0]);
    return dist[bfs_far(far)];
}
void unite(ll x,ll y){
    x=findf(x),y=findf(y);
    if(x==y) return;
    pd=max(diam[x],max(diam[y],up[x]+up[y]+1));
    fa[x]=y;
    diam[y]=pd;
    up[y]=(pd+1)/2;
}
int main(){
    cin>>n>>m>>q;
    for(i=1;i<=n;i++) fa[i]=i,diam[i]=0,up[i]=0;
    for(i=1;i<=m;i++){
        cin>>a>>b;
        ss[a].push_back(b),ss[b].push_back(a);
    }
    for(i=1;i<=n;i++) if(!vis[i]){
        nodes.clear();
        while(!q2.empty()) q2.pop();
        q2.push(i),vis[i]=1,nodes.push_back(i);
        while(!q2.empty()){
            u=q2.front(),q2.pop();
            for(j=0;j<(ll)ss[u].size();j++){
                v=ss[u][j];
                if(!vis[v]){
                    vis[v]=1,nodes.push_back(v),q2.push(v);
                }
            }
        }
        zc=tree_diam();
        pd=(zc+1)/2;
        for(j=0;j<(ll)nodes.size();j++) fa[nodes[j]]=nodes[0];
        diam[nodes[0]]=zc;
        up[nodes[0]]=pd;
    }
    while(q--){
        cin>>zc>>a;
        if(zc==1) cout<<diam[findf(a)]<<"\n";
        else{
            cin>>b;
            unite(a,b);
        }
    }
    return 0;
}