CF506D Mr. Kitayuta's Colorful Graph

好久没更新这个单题系列了，主要是最近没啥CF比赛空闲时间又少，今天忙里偷闲写了两个题

这个题就比较典了，两点是否连通一般都是想到并查集维护，现在的问题是要对每种颜色的边把贡献算清楚

很容易想到枚举所有颜色的边，每次求出所有连通分量后遍历一遍询问统计答案，这样正确性显然但复杂度是\(O(m\times (n+q))\)的

冷静思考一下会发现其实很多时候连通分量的大小和数量都很少，完全不需要我们暴力遍历所有询问，我们可以直接平方暴力枚举一个连通分量内的所有点对，然后把它对应的询问的答案更新即可

然后结合两种算法就很容易得到一个根号分治的做法，我们设阈值\(S=\sqrt m\)

对于某种颜色的边，如果其边数\(>S\)就直接跑前面的算法，否则记录下所有用到的点，遍历每个联通块即可

总复杂度\(O(m\sqrt m\times (\alpha(n)+\log n))\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=100005;
int n,m,a,b,c,q,x[N],y[N],ans[N],fa[N];
vector <pi> col[N]; vector <int> num[N]; map <pi,vector <int>> qid;
inline int getfa(CI x)
{
	return fa[x]!=x?fa[x]=getfa(fa[x]):x;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j,k; for (scanf("%d%d",&n,&m),i=1;i<=m;++i)
	scanf("%d%d%d",&a,&b,&c),col[c].push_back(pi(a,b));
	for (i=1;i<=n;++i) fa[i]=i;
	for (scanf("%d",&q),i=1;i<=q;++i)
	{
		scanf("%d%d",&x[i],&y[i]);
		if (x[i]>y[i]) swap(x[i],y[i]); qid[pi(x[i],y[i])].push_back(i);
	}
	int S=(int)sqrt(m); for (i=1;i<=m;++i)
	{
		if (col[i].size()<=S)
		{
			vector <int> pnt; for (auto [a,b]:col[i])
			pnt.push_back(a),pnt.push_back(b),fa[getfa(a)]=getfa(b);
			sort(pnt.begin(),pnt.end()); pnt.erase(unique(pnt.begin(),pnt.end()),pnt.end());
			for (auto x:pnt) num[getfa(x)].push_back(x);
			for (auto x:pnt) if (getfa(x)==x)
			{
				for (j=0;j<num[x].size();++j) for (k=j+1;k<num[x].size();++k)
				{
					a=num[x][j]; b=num[x][k]; if (a>b) swap(a,b);
					if (qid.count(pi(a,b))) for (auto it:qid[pi(a,b)]) ++ans[it];
				}
			}
			for (auto x:pnt) num[x].clear(),fa[x]=x;
		} else
		{
			for (auto [a,b]:col[i]) fa[getfa(a)]=getfa(b);
			for (j=1;j<=q;++j) ans[j]+=getfa(x[j])==getfa(y[j]);
			for (j=1;j<=n;++j) fa[j]=j;
		}
	}
	for (i=1;i<=q;++i) printf("%d\n",ans[i]);
	return 0;
}