[补]「WC2021」括号路径

[补]「WC2021」括号路径

注意到到达关系是相互的，因此可以把能够互相到达的点放到同一集合中

因此只需要考虑最简单的到达情况，发现实际上当一个点有两条同色入边时，可以将这两条边对应的点合并

对于每个集合，维护一个颜色出边的集合，可以用( ext{std::map})实现，每次合并两个点用并查集处理集合关系

然后用启发式合并的方式维护集合的边，即可做到(O(mlog^2 m))

用线段树合并的方式维护同样的东西即可做到(O(mlog k))

#include<bits/stdc++.h>
using namespace std;
enum{N=300010};
int n,m,i,u,v,w,F[N],S[N];
int Find(int x){ return F[x]==x?x:F[x]=Find(F[x]); }
map <int,int> M[N];
void U(int x,int y){
	x=Find(x),y=Find(y);
	if(x==y) return;
	if(M[x].size()>M[y].size()) swap(x,y);
	F[x]=y,S[y]+=S[x]; 
	for(auto i:M[x]) M[y].emplace(i);
	for(auto i:M[x]) U(M[y][i.first],i.second);
}
main(){
	for(scanf("%d%d%*d",&n,&m),i=1;i<=n;++i) S[F[i]=i]=1;
	while(m--){
		scanf("%d%d%d",&v,&u,&w),u=Find(u),v=Find(v);
		if(M[u].count(w)) U(M[u][w],v);
		else M[u][w]=v;
	}
	int64_t ans=0;
	for(i=1;i<=n;++i) if(Find(i)==i) ans+=1ll*S[i]*(S[i]-1)/2;
	printf("%lld
",ans);
}