「CF506D」Mr. Kitayuta's Colorful Graph

题意：给出一个 $n$ 个点，$m$ 条边的无向图，每条边上是有颜色的。有 $q$ 组询问。对于第 $i$ 组询问，给出点对 $u_i,v_i$， 求有多少种颜色 $c$，满足存在至少一条从 $u_i$ 到 $v_i$ 的路径，使得该路径上的所有边的颜色均为 $c$。

暴力分块！！！

对于不同的数据采取不同的暴力方式，即可通过这道题。

对于每种颜色，统计这种颜色的边有多少，如果大于 $\sqrt m$，那么这时满足这种情况的颜色数量 $\le \sqrt m$。建一个只含有这种颜色边的图，然后并查集判断连通性，对每个询问统计贡献；

如果小于 $\sqrt m$，那么所有连通块内点数的平方和不会超过 $n\sqrt n$，我们直接选择枚举点对算贡献即可。

最后统计答案时要用 map 统计，存边时用 vector 即可。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<ctime>
#include<map>
#define INF 1e9
using namespace std;
const int maxn=200010;
const double Pi=acos(-1.0);
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9') {f|=(ch=='-');ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	x=f?-x:x;
	return;
}
int n,m,q,fa[maxn],size[maxn],vis[maxn],qx[maxn],qy[maxn];
int head[maxn],cnt,num[maxn],r[maxn],tot;
map<pair<int,int>,int > ans,v;
vector<pair<int,int> > e[maxn],o;
int min(int a,int b)
{
	return a<b?a:b;
}
int max(int a,int b)
{
	return a>b?a:b;
}
int getfa(int u)
{
	if(fa[u]==u)
		return u;
	return fa[u]=getfa(fa[u]);
}
void merge(int a,int b)
{
	a=getfa(a);
	b=getfa(b);
	if(a!=b)
	{
		if(size[a]<size[b])
		{
			fa[a]=b;
			size[b]+=size[a];
		}
		else
		{
			fa[b]=a;
			size[a]+=size[b];
		}
	}
}
void count_question(int c)
{
	for(int i=1;i<=n;i++)
	{
		fa[i]=i;
		size[i]=1;
	}
	vector<pair<int,int> >::iterator it;
	for(it=e[c].begin();it!=e[c].end();it++)
		merge(it->first,it->second);
	for(it=o.begin();it!=o.end();it++)
	{
		int a=min(it->first,it->second);
		int b=max(it->first,it->second);
		if(getfa(a)==getfa(b))
			++ans[make_pair(a,b)];
	}
}
void count_points(int c)
{
	memset(vis,0,sizeof(vis));
	tot=0;
	vector<pair<int,int> >::iterator it;
	for(it=e[c].begin();it!=e[c].end();it++)
	{
		if(!vis[it->first])
		{
			r[++tot]=it->first;
			fa[r[tot]]=r[tot];//初始化fa和size一定只对这种颜色的点更新！！！否则会TLE！！！
			size[r[tot]]=1;
			vis[it->first]=1;
		}
		if(!vis[it->second])
		{
			r[++tot]=it->second;
			fa[r[tot]]=r[tot];
			size[r[tot]]=1;
			vis[it->second]=1;
		}
		merge(it->first,it->second);
	}
	for(int i=1;i<=tot;i++)
		for(int j=i+1;j<=tot;j++)
			if(r[i]!=r[j])
			{
				int a=min(r[i],r[j]);
				int b=max(r[i],r[j]);
				int x=getfa(a);
				int y=getfa(b);
				if(x==y)
					++ans[make_pair(a,b)];
			}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		num[c]++;
		e[c].push_back(make_pair(min(a,b),max(a,b)));
	}
	scanf("%d",&q);
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d",&qx[i],&qy[i]);
		if(!ans.count(make_pair(min(qx[i],qy[i]),max(qx[i],qy[i]))))
		{
			o.push_back(make_pair(min(qx[i],qy[i]),max(qx[i],qy[i])));
			ans[make_pair(min(qx[i],qy[i]),max(qx[i],qy[i]))]=0;
		}
	}
	for(int i=1;i<=m;i++)
		if(num[i])
		{
			if(num[i]>=sqrt(m))
				count_question(i);
			else
				count_points(i);
		}
	for(int i=1;i<=q;i++)
		printf("%d\n",ans[make_pair(min(qx[i],qy[i]),max(qx[i],qy[i]))]);
	return 0;
}