CF506D

这里提供另外一种不同的做法： `bitset` +小型暴力 想到对于每个颜色连通块，如果询问点同时属于一个颜色连通块集合，则贡献+1。 想法是对于每个点找到属于的连通块，用 `bitset` 合并计算贡献。 发现颜色连通块个数可能达到 $m$ 级别为 $10^5$ ， `bitset` 开不下，考虑优化，一个简单的想法是对于数量较小的连通块可以暴力 $O(n^2)$ 使用 `map` 储存。 设连通块大小为 $s$ 于是，当 $s\le10$ 的时候选择 $O(n^2)$ 处理出节点，放进 `map` ，剩下的 $s\ge 10^{5-1} = 10^4$ 使用 `bitset` 储存，复杂度 $10^2\times \log n+10^{5+4}/64$轻松跑过。 ```cpp #include<bits/stdc++.h> #define ll long long using namespace std; char gc(){static char buf[1<<16],*s,*t;if(s==t){t=(s=buf)+fread(buf,1,1<<16,stdin);if(s==t)return EOF;}return*s++;} //#define getchar gc ll read() { char c; ll w=1; while((c=getchar())>'9'||c<'0')if(c=='-')w=-1; ll ans=c-'0'; while((c=getchar())>='0'&&c<='9')ans=(ans<<1)+(ans<<3)+c-'0'; return ans*w; } bitset<10005>bit[100005]; map<pair<int,int>,int>mp;//n^2部分，总数不多 const int xx=1e5+5; int n,m,fa[xx],vis[xx]; int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);} struct node{int a,b,c;bool operator<(const node&w)const{return c<w.c;};}e[xx]; vector<int>v[xx]; signed main(){ n=read(),m=read(); for(int i=1;i<=m;i++)e[i].a=read(),e[i].b=read(),e[i].c=read(); sort(e+1,e+m+1); int tt=0; for(int i=1;i<=m;i++) { int l=i,r=i; while(r<m&&e[r+1].c==e[r].c)r++; vector<int>use; for(int j=l;j<=r;j++) { if(!vis[e[j].a])use.push_back(e[j].a),vis[e[j].a]=1; if(!vis[e[j].b])use.push_back(e[j].b),vis[e[j].b]=1; } for(auto it:use)vis[it]=0,fa[it]=it; for(int j=l;j<=r;j++)fa[find(e[j].a)]=find(e[j].b); for(auto it:use)v[find(it)].push_back(it); for(auto it:use) { if(v[it].size()) { if(v[it].size()<=10) { for(auto a:v[it]) { for(auto b:v[it]) { if(a>=b)continue; mp[make_pair(a,b)]++; } } } else { tt++; for(auto a:v[it])bit[a][tt]=1; } v[it].clear(); } } i=r; } int q=read(); while(q--) { int a=read(),b=read(); if(a>b)swap(a,b); // cout<<mp[make_pair(a,b)]<<"\n"; cout<<mp[make_pair(a,b)]+(bit[a]&bit[b]).count()<<"\n"; } return 0; } ```