Mr. Kitayuta's Colorful Graph

· · 题解

Mr. Kitayuta's Colorful Graph

根号分治入门题解。

分析

在线蒟蒻肯定做不了，于是把询问离线下来。

因为不同颜色的边之间不会互相影响，所以能够朴素地想到对于每种颜色的边进行计数。

当某种颜色的边很少时，其连接的点就很少；当某种颜色的边很多时，则这种（边连接的点很多的）颜色的种类很少（原因是总边数固定），此时其连接的点就很多。

所以某种颜色的边数少时，我们可以拼上关于连接的点数的暴力；边数多时，我们可以拼上关于边的种类的暴力。

即对于每个颜色的边数进行分治，但分治的条件还不知道，求一下。

对于边数多于或等于 B 的颜色，因为这种颜色少于或等于 \frac{m}{B} 个，所以我们对于每个询问使用并查集暴力判连通性计数，时间复杂度：

对于边数少于 $B$ 的颜色，因为总共 $m$ 条边，每个这种颜色的边连接 $2B$ 个点，所以所有这种颜色连接的点的总数量少于 $2mB$，所以对于这种颜色连接的点两两用并查集判连通性并使用 unordered_map 计数，时间复杂度：$\large O(mB)$。 平衡一下，$B$ 取 $\sqrt{m}$ 是个不错的选择，时间复杂度：$\large O((q+m)\sqrt{m}\alpha(n))$。 实现时，由于 unordered_map 还得把 pair 转换一下有点难受，于是直接使用了 map，代码实际时间复杂度为：$\large O((q+m \log n)\sqrt{m}\alpha(n))

实现是相对容易的，详见 AC CODE 部分。

总结

你会发现，在对 b 有关量分治时。我将两个时间复杂度为 O(\frac{ab}{B}) 和 O(cB) 的暴力拼起来，B 取 \sqrt{b} 左右时最优（当然要考虑常数），此乃根号分治也。

其实根号分治在思考过程中的关键就是找到被分治量与其他某个量的反比例关系以及与其他另一个量的正比例关系，然后对于“某个量”和“其他另一个量”拼上两个解法。

注意

对于两个点的答案，map 统计时统一统计为编号小的点到编号大的点以方便查询。

AC CODE

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
using namespace std;
map<pii,int> mp;
struct edge{
    int x,y;
    int id;
}e[200005];
int n,m,q;
int q1[200005],q2[200005];
int fa[100005];
int a[200005];
int ans[200005];
int find(int x){
    if(fa[x]==x){
        return fa[x];
    }
    return fa[x]=find(fa[x]);
}
void merge(int x,int y){
    int fx=find(x),fy=find(y);
    if(fx!=fy){
        fa[fy]=fx;
    }
}
bool cmp(edge a,edge b){
    return a.id<b.id;
}
int main(){
    cin>>n>>m;
    int Q=sqrt(m);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        e[i].id=w;
        if(u>v) swap(u,v);
        e[i].x=u,e[i].y=v;
    }
    sort(e+1,e+1+m,cmp);
    cin>>q; 
    for(int i=1;i<=q;i++){
        int x,y;
        cin>>x>>y;
        if(x>y) swap(x,y);
        q1[i]=x,q2[i]=y;
    }
    for(int i=1;i<=m;i++){
        int j=i;
        while(e[j].id==e[j+1].id) j++;
        int num=j-i+1;
        for(int k=i;k<=j;k++){
            int fx=find(e[k].x),fy=find(e[k].y);
            if(fx!=fy) fa[fy]=fx;
        }
        if(num<=Q){
            int idx=0;
            for(int k=i;k<=j;k++){
                a[++idx]=e[k].x;
                a[++idx]=e[k].y;
            }
            sort(a+1,a+1+idx);
            idx=unique(a+1,a+1+idx)-a-1;
            for(int u=1;u<=idx;u++){
                for(int v=u+1;v<=idx;v++){
                    if(find(a[u])==find(a[v])){
                        mp[mkp(a[u],a[v])]++;
                    }
                }
            }
        }else{
            for(int k=1;k<=q;k++){
                if(find(q1[k])==find(q2[k])) ans[k]++;
            }
        }
        for(int k=i;k<=j;k++){
            int x=e[k].x,y=e[k].y;
            fa[x]=x,fa[y]=y;
        }
        i=j;
    }
    for(int i=1;i<=q;i++){
        if(mp.find(mkp(q1[i],q2[i]))!=mp.end()) ans[i]+=mp[mkp(q1[i],q2[i])];
        cout<<ans[i]<<"\n";
    }
    return 0;
}