【CF思维训练】CF1804F Approximate Diameter

小木虫 · 2023-03-17 15:50:41 · 题解

Preface

十分有趣的一道思维题。

Problem

给你一个 n 个点，m 条边的无向图，现在有 q 次加边操作，你需要在一开始以及每一次加边后输出这个无向图的直径的模糊值 a_i，使得：

其中 d 表示图的直径，G_i 代表第 i 次加边结束之后的无向图。
数据范围：n,m,q\leq 10^5。

Solution

观察这道题，发现这个输出模糊值的设定十分有趣。
你发现，如果想求出一个无向图的具体直径是 O(n^2) 的，你需要对每一个点开始做一次 BFS 才能求解。

但是你注意到，你设 \alpha(G,s) 为对于无向图 G，从 s 开始 BFS，离他最远的点离他的距离，你会发现无论 s 取什么值， \alpha(G,s) 都始终满足：

这和模糊值的定义式非常相似。
关于证明，对于直径上的 s，这个结论显然，而对于不在直径上的点，你可以先走到直径上，然后也可以得到这个结论。

继续探究，你发现对于每一次加边，对于任意 \alpha(G,s) 肯定是变小的。
你只需要把 BFS 搜索树建出来，这个操作实际上等于移植一棵子树，这最多会导致 \alpha(G,s) 折半。

你把所有的操作离线下来，由于模糊值的定义式允许你小于等于直径的二倍，那么你自然而然地想到，你一次算出的 \alpha 可以被使用多次，直到直径变为其一半。
直径太不好处理了，我们干脆把他也变成 \alpha，现在问题就是你可以用一个 \alpha 值直到一个时间点，使这个时间点的 \alpha 为它的一半。
这个太好做了，我们直接可以二分跳到哪个节点。

然后你发现，由于每一次跳跃会使答案除二，你最多会跳跃 \log n 次，二分后继的复杂度是 O(\log n) 的，你做一次 BFS 计算 \alpha 的复杂度是 O(n) 的，总复杂度就是 O(n \log ^2 n)：

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=2e5+10;
int n,m,q,u[N],v[N],dep[N];
vector <int> edge[N];
queue <int> Q;
int BFS(){int res=0;
    for(int i=1;i<=n;i++)
        dep[i]=1e9;
    Q.push(1);dep[1]=0;
    while(Q.size()){
        int u=Q.front();
        for(auto v:edge[u]){
            if(dep[v]>dep[u]+1)
                dep[v]=dep[u]+1,Q.push(v);
        }
        if(Q.size()==1)
            res=dep[u];
        Q.pop();
    }return res;
}
int check(int x){
    for(int i=1;i<=x;i++)
        edge[u[i]].pb(v[i]),edge[v[i]].pb(u[i]);
    int tmp=BFS();//cout<<"debug: "<<x<<" "<<tmp<<endl;
    for(int i=x;i>=1;i--)
        edge[u[i]].pop_back(),edge[v[i]].pop_back();
    return tmp;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++){
        cin>>u[0]>>v[0];
        edge[u[0]].pb(v[0]),edge[v[0]].pb(u[0]);
    }for(int i=1;i<=q;i++)cin>>u[i]>>v[i];
    for(int i=0;i<=q;i++){
        int now=check(i);
        int l=i,r=q;
        while(l<r){
            int mid=(l+r+1)/2;
            if(check(mid)*2<now)
                r=mid-1;
            else l=mid;
        }
        for(int j=i;j<=l;j++)cout<<now<<" ";
        i=l;
    }
    return 0;
}