brute force ? 其实是平方分解。很容易想到的是每一个颜色建一个图，然后并查集维护一下连通性。
问题在于颜色有O(m)种，每种颜色的图点数都是O(n)的，因此并查集的空间只能重复利用。
但是可以把以O(m)的空间把有用的连通块信息保留下来。
之后的处理可以借鉴分块的思想。
记点v属于的连通块数量为b(v)，对于询问x,y ，根据点所在的连通块信息，可以以O(max(b(x),b(y)))的时间回答出来。
设置一个阀值B，对于b(v)>B，提前预处理，小于B的就暴力回答。
因为一条边最多增加两个b(v)值，所有b(v)的和是O(m)的。 最多有m/B个v满足b(v)大于B，对于每个这样的v，O(m)历遍，O(m)的空间记录答案。
两部分的复杂度是O(m/B*m + B*q)，类似分块的取法，取B = m/sqrt(q)，复杂度为O(m*sqrt(q))。
/********************************************************* * --------------Alfheim-------------- * * author AbyssalFish * **********************************************************/ #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5+5, maxm = 1e5+5; int pa[maxn], rak[maxn]; int fd(int x) { return pa[x]? pa[x] = fd(pa[x]): x; } inline void joint(int a,int b) { int x = fd(a), y = fd(b); if(x != y){ if(rak[x] < rak[y]){ pa[x] = y; } else { pa[y] = x; if(rak[x] == rak[y]) rak[x]++; } } } int a[maxm],b[maxm]; bool vis[maxn]; int hd_c[maxn], nx_e[maxm]; inline void add_e(int cl,int i) { nx_e[i] = hd_c[cl]; hd_c[cl] = i; } typedef vector<int> Block; typedef vector<int> v_int; vector<Block> blc; Block tmp[maxn]; v_int in_blk[maxn]; inline void add_blc(int x) { if(!vis[x]){ vis[x] = true; tmp[fd(x)].push_back(x); } } inline void dump(int x) { if(tmp[x].size() > 1){ blc.push_back(tmp[x]); tmp[x].clear(); } if(vis[x]){ vis[x] = false; rak[x] = pa[x] = 0; } } const uint32_t MAXB = 448; int ans[MAXB+5][maxn]; int id[maxn]; //#define LOCAL int main() { #ifdef LOCAL freopen("in.txt","r",stdin); #endif //cout<<(2*maxm/sqrt(2*maxm)); int n,m,q; scanf("%d%d",&n,&m); uint32_t B = floor(2*m/sqrt(2*m)); int i,j; for(i = 1; i <= m; i++){ scanf("%d%d%d",a+i,b+i,&j); add_e(j,i); } for(i = 1; i <= m; i++){ for(j = hd_c[i]; j; j = nx_e[j]){ joint(a[j],b[j]); } for(j = hd_c[i]; j; j = nx_e[j]){ add_blc(a[j]); add_blc(b[j]); } for(j = hd_c[i]; j; j = nx_e[j]){ dump(a[j]); dump(b[j]); } } for(i = 0; i < (int)blc.size(); i++){ for(auto v: blc[i]){ in_blk[v].push_back(i); } } int id_cnt = 0; for(i = 1; i <= n; i++){ if(in_blk[i].size() > B){ id[i] = ++id_cnt; for(auto b_id: in_blk[i]){ for(auto v: blc[b_id]){ ans[id_cnt][v]++; } } } } scanf("%d",&q); while(q--){ int x,y; scanf("%d%d",&x,&y); int res; if(id[x]) res = ans[id[x]][y]; else if(id[y]) res = ans[id[y]][x]; else { res = i = j = 0; v_int &X = in_blk[x], &Y = in_blk[y]; n = X.size(); m = Y.size(); while(i < n && j < m){ if(X[i] == Y[j]){ res++; i++; j++; } else { X[i] < Y[j] ? i++ : j++; } } } printf("%d ",res); } return 0; }