Description：

一个可能存在重边但没有自环的无向图。每条边有一种属性和一个权值。属性可能是 $R$ 、 $G$ 、 $B$ 三种当中的一种，一个三元环（首尾相接的三条边，其中 $R$ 、 $G$ 、 $B$ 三种边各一条）产生的能量是其中三条边的权值之积，求图的总能量。

$1\le N \le5\times 10^4\ \ \ 1\le M \le 10^5$

Solution：

发现没有什么数据结构可以用，也找不出什么算法，数据范围又很奇怪，很有可能是根号分治。

因为边数只有 $m$ 个，所以度数大于 $\sqrt m$ 的点只有不超过 $\sqrt m$ 个，可以暴力枚举这三个点统计答案， $O(m\sqrt m)$ 。

对于三元环中有小点的情况，可以枚举小点的所有出边，并判断另两个点有没有对应的边，为了不重不漏只枚举环中编号最小的点，发现枚举第一条出边相当于枚举图内的所有边，枚举第二条边 $O(\sqrt m)$ ，于是复杂度 $O(m\sqrt m)$

用 $map$ 复杂度加一个 $log$

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 50010

#define MOD 1000000007

map<char,int> p;

typedef long long ll;

map<pair<int,int>,ll> g[3];

char getc()

{

	char c = getchar();

	while(c != 'R' && c != 'G' && c != 'B')c = getchar();

	return c;

}

#define MAXM 100010

struct edge

{

	int to,nxt,c;

	ll v;

}e[MAXM << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int c,int d)

{

	++edgenum;e[edgenum].to = b;e[edgenum].v = (ll)c;e[edgenum].c = d;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].v = (ll)c;e[edgenum].c = d;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

int deg[MAXN];

int bigger[MAXN],ptr1 = 0;

int smaller[MAXN],ptr2 = 0;

ll query(int a,int b,int c)

{

	ll res = 0;

	for(int i = 0;i <= 2;++i)

	{

		for(int j = 0;j <= 2;++j)

		{

			if(i == j)continue;

			for(int k = 0;k <= 2;++k)

			{

				if(i == k || j == k)continue;

				if(g[i].find(make_pair(a,b)) != g[i].end() && g[j].find(make_pair(b,c)) != g[j].end() && g[k].find(make_pair(c,a)) != g[k].end())

				{

					res = (res + g[i][make_pair(a,b)] * g[j][make_pair(b,c)] % MOD * g[k][make_pair(c,a)] % MOD) % MOD;

				}

			}

		}

	}

	return res;

}

bool tag[MAXN];

int main()

{

	scanf("%d%d",&n,&m);

	p['R'] = 0;p['G'] = 1;p['B'] = 2;

	int a,b,c,d;

	memset(deg,0,sizeof(deg));

	memset(tag,false,sizeof(tag));

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d",&a,&b,&c);

		d = p[getc()];

		g[d][make_pair(a,b)] = (g[d][make_pair(a,b)] + (ll)c) % MOD;

		g[d][make_pair(b,a)] = (g[d][make_pair(b,a)] + (ll)c) % MOD;

		add(a,b,c,d);

		++deg[a];++deg[b];

	}

	int siz = sqrt(m);

	for(int i = 1;i <= n;++i)

	{

		if(deg[i] > siz)bigger[++ptr1] = i;

		else

		{

			smaller[++ptr2] = i;

			tag[i] = true;

		}

	}

	ll ans = 0;

	for(int i = 1;i <= ptr1;++i)

	{

		for(int j = i + 1;j <= ptr1;++j)

		{

			for(int k = j + 1;k <= ptr1;++k)

			{

				ans = (ans + query(bigger[i],bigger[j],bigger[k])) % MOD;

			}

		}

	}

	for(int k = 1;k <= ptr2;++k)

	{

		for(int i = lin[smaller[k]];i != 0;i = e[i].nxt)

		{

			if(tag[e[i].to] && e[i].to < smaller[k])continue;

			for(int j = e[i].nxt;j != 0;j = e[j].nxt)

			{

				if(e[i].c == e[j].c || (tag[e[j].to] && e[j].to < smaller[k]))continue;

				int last = 3 - e[i].c - e[j].c;

				if(g[last].find(make_pair(e[i].to,e[j].to)) != g[last].end())

				{

					ans = (ans + e[i].v * e[j].v % MOD * g[last][make_pair(e[i].to,e[j].to)] % MOD) % MOD;

				}

			}

		}

	}

	cout << ans << endl;

	return 0;

}