传送门：点击打开链接
题意：1e5个点的无向图，求三元环(u,v,s),u<v，满足u经过路径到达v，把路径上经过的边的值求异或和等于s。三元环的价值为s。现在求所有三元环的总价值之和。
思路：可能有很多个连通块，对每个连通块考虑。
首先，我们考虑，如果这个连通块只是一棵树的话。我们对每一位去考虑，直接通过计数就能得到答案。
但是现在图上还有很多环，我们可以发现，环的答案可以直接异或到链上去，我只要走到环上，再绕环一圈，再走回来，就能恰好只异或了环上的值。
所以我们求出所有的环，对环求一遍线性基。
之后的做法，我们前面说的树相当于现在的DFS搜索树，直接对这个树去讨论计数，只要认真讨论一下，答案非常简单就能推导出来的.
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <bitset>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <functional>
#define fuck(x) cout<<"["<<x<<"]";
#define FIN freopen("input.txt","r",stdin);
#define FOUT freopen("output.txt","w+",stdout);
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;const int MX = 5e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;struct Edge {LL val;int v, nxt;
} E[MX];
int Head[MX], erear;
void edge_init() {erear = 0;memset(Head, -1, sizeof(Head));
}
void edge_add(int u, int v, LL val) {E[erear].v = v;E[erear].val = val;E[erear].nxt = Head[u];Head[u] = erear++;
}int n, m, sz, r;
LL A[MX], P[62], dis[MX];
vector<int> path;LL power(LL a, LL b) {LL ret = 1;while(b) {if(b & 1) ret = ret * a % mod;a = a * a % mod;b >>= 1;}return ret;
}void DFS(int u, LL s) {if(dis[u] == -1) {dis[u] = s;} else {A[++sz] = dis[u] ^ s;return;}path.push_back(u);for(int i = Head[u]; ~i; i = E[i].nxt) {int v = E[i].v;DFS(v, s ^ E[i].val);}
}void Guass_base() {memset(P, 0, sizeof(P));for(int i = 1; i <= sz; i++) {for(int j = 62; j >= 0; j--) {if(!(A[i] >> j & 1)) continue;if(!P[j]) {P[j] = A[i]; break;}A[i] ^= P[j];}}r = 0;for(int i = 62; i >= 0; i--) {if(P[i]) r++;}
}LL solve() {Guass_base();LL ans = 0;for(int i = 62; i >= 0; i--) {int cnt[2] = {0}, sign = 0;for(int j = 62; j >= 0; j--) {if(P[j] >> i & 1) sign = 1;}for(int j = 0; j < path.size(); j++) {int u = path[j];if(sign) ans += power(2, i + r - 1) * j % mod;else ans += power(2, i + r) * cnt[!(dis[u] >> i & 1)] % mod;ans %= mod;cnt[dis[u] >> i & 1]++;}}return ans;
}int main() {// FIN;edge_init();scanf("%d%d", &n, &m);memset(dis, -1, sizeof(dis));for(int i = 1; i <= m; i++) {int u, v; LL val;scanf("%d%d%I64d", &u, &v, &val);edge_add(u, v, val);edge_add(v, u, val);}LL ans = 0;for(int i = 1; i <= n; i++) {if(dis[i] == -1) {path.clear(); sz = 0;DFS(i, 0);ans += solve();ans %= mod;}}printf("%I64d\n", ans);return 0;
}