题解 CF506D Mr. Kitayuta's Colorful Graph

神仙题。

暴力+暴力=AC。

没错，先想出两个暴力，然后拼起来，你就 AC 了这道题。

用分块来选择用哪个暴力，可能也是一种正解的做法。

首先我们能想到最无脑的暴力 1 。

暴力 1

对于每种颜色建一个仅含有这一种颜色的边的图，然后用并查集判连通，扫一次所有询问统计贡献。

时间复杂度：首先 $\operatorname{O}(m)$ 的枚举颜色，然后 $\operatorname{O}(n\alpha(n))$ 的建图+并查集（其实建图可以不用，直接并查集就够了），再加上 $\operatorname{O}(q\alpha(n))$ 的处理询问。总时间复杂度 $\operatorname{O}(m\alpha(n)(n+q))$ 。

这显然是过不了这道题的，那么我们再来想另一个暴力。

暴力 2

其实只是对暴力 1 的一点修改。

对于每种颜色建一个仅含有这一种颜色的边的图，然后用并查集判连通，在每个连通块内枚举所有的点对 $(u,v)$ ，更新 $(u,v)$ 这个点对的贡献。

这个东西在连通块很小（连通块大小的平方小于 $q$ ）的时候会比暴力 1 更优一些。

时间复杂度：首先 $\operatorname{O}(m)$ 的枚举颜色，然后 $\operatorname{O}(n\alpha(n))$ 的建图+并查集（其实建图可以不用，直接并查集就够了），然后 $\operatorname{O}(n^2\alpha(n))$ 的算贡献。总时间复杂度 $\operatorname{O}(mn^2\alpha(n))$。

正解

那么，我们就想到：可不可以在连通块大小的平方小于 $q$ 的时候用暴力 2 ，而在连通块大小的平方大于 $q$ 的时候再用暴力 1 呢？

当然可以。

什么时候一个颜色的图中每个连通块大小的平方都小于 $q$ ？

在 该颜色边数 $<\sqrt{m}$ 的时候，所有这种颜色的所有连通块内点数的平方和不会超过 $n\sqrt n$ 。

于是，暴力 2 就可以胜任这部分的任务，复杂度 $\operatorname{O}(n\alpha(n)\sqrt n)$。

在 该颜色边数 $\ge\sqrt{m}$ 的时候，我们就可以用暴力 1 ，因为此时满足这种情况的颜色数量只会 $\le\sqrt m$。这样的话再扫一遍所有询问，复杂度是 $\operatorname{O}(\sqrt m(q\alpha(q)))$ 的。

这样，两个暴力拼起来，就打出了正解。

考虑实现统计答案时用 map 统计，复杂度应乘上 $\operatorname{O}(\log q)$。所以，总复杂度为：$\operatorname{O}((n\alpha(n)\sqrt n+\sqrt m(q\alpha(q)))\log q)$ 。

Code

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int N=200005;
int n,m,q;
int num[N];
vector<pair<int,int> > e[N],qs;
map<pair<int,int>,int> ans,lst;
int f[N],sz[N],qto[N];
int find(int i) {return f[i]==i?i:f[i]=find(f[i]);}
void merge(int u,int v) {
    u=find(u);v=find(v);
    if(u!=v) {
        if(sz[u]>sz[v]) {
            f[v]=u;
            sz[u]+=sz[v];
        } else {
            f[u]=v;
            sz[v]+=sz[u];
        }
    }
}
void bao1(int co) {
    rep(i,1,n) f[i]=i,sz[i]=1;
    for(vector<pair<int,int> >::iterator ii=e[co].begin();ii!=e[co].end();++ii) {
        merge(ii->first,ii->second);
    }
    for(vector<pair<int,int> >::iterator ii=qs.begin();ii!=qs.end();++ii) {
        int u=ii->first,v=ii->second;
        u=find(u),v=find(v);
        if(u==v) {
            ++ans[make_pair(ii->first,ii->second)];
        }
    }
}
void bao2(int co) {
    int ps[N],tot=0;
    for(vector<pair<int,int> >::iterator ii=e[co].begin();ii!=e[co].end();++ii) {
        ps[++tot]=ii->first;
        ps[++tot]=ii->second;
    }
    sort(ps+1,ps+tot+1);
    tot=unique(ps+1,ps+tot+1)-ps-1;
    rep(i,1,tot) f[ps[i]]=ps[i],sz[ps[i]]=1;
    for(vector<pair<int,int> >::iterator ii=e[co].begin();ii!=e[co].end();++ii) {
        merge(ii->first,ii->second);
    }
    rep(i,1,tot) {
        rep(j,i+1,tot) {
            bool flg=0;
            int u=find(ps[i]),v=find(ps[j]);
            if(u==v) flg=1;
            if(flg&&ans.count(make_pair(ps[i],ps[j]))) {
                ans[make_pair(ps[i],ps[j])]++;
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    rep(i,1,m) {
        int u,v,c;
        scanf("%d%d%d",&u,&v,&c);
        num[c]++;e[c].push_back(make_pair(min(u,v),max(u,v)));
    }
    scanf("%d",&q);
    int now=0;
    rep(i,1,q) {
        int u,v;
        scanf("%d%d",&u,&v);
        if(!ans.count(make_pair(min(u,v),max(u,v)))) {
            qs.push_back(make_pair(min(u,v),max(u,v)));
            ++now;
            lst[make_pair(min(u,v),max(u,v))]=now;
            qto[i]=now;
        }
        else qto[i]=lst[make_pair(min(u,v),max(u,v))];
        ans[make_pair(min(u,v),max(u,v))]=0;
    }
    rep(i,1,m) {
        if(num[i]) {
            if(num[i]>=sqrt(m)) {
                bao1(i);
            } else bao2(i);
        }
    }
    rep(i,1,q) {
        int u=qs[qto[i]-1].first,v=qs[qto[i]-1].second;
        printf("%d\n",ans[make_pair(u,v)]);
    }
    return 0;
}