[Codeforces 506D]Mr. Kitayuta's Colorful Graph

挖咧，這題$N$好大、$M$好大、$Q$也好大
不知從何下手，好慘QAQ

沒關係，我們先來想想看會TLE的作法

可以發現，每一個顏色是獨立的，因此乾脆把邊依照顏色分別存放，query的時候就每個顏色檢查看看會不會連通，答案即是讓兩點連通的顏色數量

為了方便說明，令$E_{c}$為顏色是$c$的邊的集合

咦，連通？那不就可以用並查集維護了嗎？
這樣一來，每個顏色$c$的query可以做到$O(\alpha(n))$ ($n$是$E_{c}$涵蓋的點集的大小)

可是，如果顏色太多，就GG惹Orz

如果顏色非常多，但每種顏色的邊非常少的話，我們其實可以套用另外一個做法
對於每種顏色
把它的連通狀態算出來之後，因為涵蓋的點數非常少，那乾脆把所有點對枚舉一遍，將結果存在類似$map<pair<int,int>,int>$的資料結構裡面
每個顏色都像這樣枚舉一次，這樣我們就可以做到$O(\log N)$查詢任意點對的連通顏色數了！

咦？好像發現了甚麼
第一個做法適用顏色少、同一個顏色的邊數多的情況
第二個做法適用顏色多、同一個顏色的邊數少的情況

那我們乾脆把$E_{c}$依照大小分類

當$E_{c}$的大小$>\sqrt{M}$的時候，套用第一種作法 (稱第一大類)

當$E_{c}$的大小$\leq \sqrt{M}$的時候，套用第二種作法 (稱第二大類)

然後query的時候就把這兩大類的答案加起來就好了

這樣複雜度多少呢？

對於並查集們的預處理

如果並查集套用離散化和動態調整大小，可以做到$O(M\log M+N+M\alpha(N))$ (離散化+並查集初始化+合併被邊連接的兩點)

對於第一大類的query

可以發現，大小$>\sqrt{M}$的$E_{c}$不會超過$O(\sqrt{M})$個

因此query的時間複雜度是$O(\sqrt{M}\alpha(N))$

對於第二大類的預處理

最糟糕的情況想必是每個$E_{c}$都是最大的大小 (也就是$\sqrt{M}$)，這樣一來處理每個顏色需要$O(\sqrt{M}^{2})=O(M)$的時間，但這時最多$O(\sqrt{M})$種顏色，因此總時間複雜度不會超過$O(M\sqrt{M})$
至於為甚麼「每個$E_{c}$都是最大的大小 」是最糟的情況，可以想像一下將它們$DP$求最大值的過程，會發現每一段應該盡量大，才能充分運用平方的增量效果(?)

對於第二大類的query
由於已經將所有答案預處理好，query只需要$O(\log N)$

時間複雜度：$O(M\log M+N+M\alpha(N)+\max(Q\sqrt{M}\alpha(N),M\sqrt{M}+Q\log N))$ (實際上我的並查集並沒有特別優化，複雜度是$O(\log N)$而不是$O(\alpha(N))$)

code:

#include<cstdio>
#include<cassert>
#include<cmath>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
struct DjSet
{
    vector<int>data,elements;
    void Clear(const vector<int>&_elements)
    {
        elements.clear();
        for(const int i:_elements)elements.push_back(i);
        vector<int>&e=elements;
        sort(e.begin(),e.end()),e.resize(unique(e.begin(),e.end())-e.begin());
        data.resize(elements.size());
        for(int i=0;i<(int)data.size();i++)data[i]=i;
    }
    bool Contains(const int v)
    {
        const auto it=lower_bound(elements.begin(),elements.end(),v);
        return it!=elements.end()&&(*it)==v;
    }
    int Id(const int v)
    {
        const auto it=lower_bound(elements.begin(),elements.end(),v);
        assert(it!=elements.end()&&(*it)==v);
        return it-elements.begin();
    }
    int FindBase(const int a){return data[a]==a?a:(data[a]=FindBase(data[a]));}
    int Find(const int a){return FindBase(Id(a));}
    bool Merge(int a,int b){if((a=Find(a))==(b=Find(b)))return false;data[a]=b;return true;}
    void OutputAllPairs(map<pair<int,int>,int>&ans)
    {
        vector<vector<int> >s;s.resize(data.size());
        for(int i=0;i<(int)data.size();i++)s[FindBase(i)].push_back(i);
        for(const vector<int>&v:s)
        {
            for(int i=0;i<(int)v.size();i++)for(int j=i+1;j<(int)v.size();j++)
            {
                ans[make_pair(elements[v[i]],elements[v[j]])]++;
                ans[make_pair(elements[v[j]],elements[v[i]])]++;
            }
        }
    }
};
vector<DjSet>BIG_COLORS;
struct Edge
{
    int a,b;
    Edge(){}
    Edge(const int _a,const int _b):a(_a),b(_b){}
};
vector<Edge>EDGE[100000];
int N,M;
map<pair<int,int>,int>ANS;
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d%d",&N,&M)==2)
    {
        for(int i=0;i<M;i++)EDGE[i].clear();
        for(int i=0,a,b,c;i<M;i++)
        {
            scanf("%d%d%d",&a,&b,&c),c--;
            EDGE[c].push_back(Edge(a,b));
        }
        const int sq_m=sqrt(M);
        ANS.clear(),BIG_COLORS.clear();
        for(int i=0;i<M;i++)if(!EDGE[i].empty())
        {
            static DjSet dj;
            vector<int>elements;
            for(const Edge &e:EDGE[i])elements.push_back(e.a),elements.push_back(e.b);
            dj.Clear(elements);
            for(const Edge &e:EDGE[i])dj.Merge(e.a,e.b);
            if((int)EDGE[i].size()<=sq_m)dj.OutputAllPairs(ANS);
            else BIG_COLORS.push_back(dj);
        }
        int querycount;scanf("%d",&querycount);
        for(int a,b;querycount--;)
        {
            scanf("%d%d",&a,&b);
            int ans=0;
            if(true)
            {
                const auto it=ANS.find(make_pair(a,b));
                if(it!=ANS.end())ans+=it->second;
            }
            for(DjSet &dj:BIG_COLORS)if(dj.Contains(a)&&dj.Contains(b)&&dj.Find(a)==dj.Find(b))ans++;
            printf("%d\n",ans);
        }
    }
    return 0;
}