1218D - Xor Spanning Tree - CodeForces Solution

// RADHASOAMI , WITH THE GRACE OF HUZUR I PROMISE TO FIGHT TILL THE LAST SECOND OF EVERY CONTEST AND str TO MY FULL POTENTIAL ......

#include <iostream>
#include <vector>
#include <unordered_map>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <chrono>
#include <random>

using namespace std;

#define ll long long int
#define pb push_back
#define mp(u,v) make_pair(u,v)

const int mod=1e9+7,I=742744451,N=131072,M=N+1005;
int n,m,tot,tim,dfn[M],fa[M],W[M],cnt[M],vis[M],C[M];
vector<pair<int,int> > E[M];
int Add(int x) { return (x>=mod?x-mod:x); }
void DFT(int *a,int op) {
	for (int i=1; i<N; i<<=1) 
		for (int j=0; j<N; j+=(i<<1))
			for (int k=0; k<i; k++) {
				int x=a[j+k],y=a[i+j+k];
				a[j+k]=Add(x+y),a[i+j+k]=Add(x-y+mod);
			}
	if (op==1) { for (int i=0; i<N; i++) a[i]=1ll*a[i]*I%mod; }
}
void FWT(int* B,int *C) {
	DFT(B,0),DFT(C,0);
	for (int i=0; i<N; i++) cnt[i]=1ll*cnt[i]*C[i]%mod,B[i]=1ll*B[i]*C[i]%mod;
	DFT(B,1);
}
void dfs(int u) {
	dfn[u]=(++tim);
	for (auto P: E[u]) {
		int v=P.first,w=P.second;
		if (v==fa[u]) continue;
		if (!dfn[v]) fa[v]=u,W[v]=w,dfs(v);
		else if (dfn[v]<dfn[u]) {
			for (int i=u; i!=v; i=fa[i]) C[W[i]]++;
			C[w]++;
			FWT(vis,C);
			for (int i=0; i<N; i++) vis[i]=min(vis[i],1),C[i]=0;
		}
	}
}
int main() {
   ios_base::sync_with_stdio(false); 
  cin.tie(NULL);
  cout.tie(NULL);
  #ifndef ONLINE_JUDGE
    freopen("input2.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
  #endif
    scanf("%d%d",&n,&m);
    for (int i=1,u,v,w; i<=m; i++) scanf("%d%d%d",&u,&v,&w),E[u].pb(mp(v,w)),E[v].pb(mp(u,w)),tot^=w;
    cnt[0]=vis[0]=1; 
 	DFT(cnt,0);
	dfs(1);
	DFT(cnt,1);
    for (int i=0; ; i++) 
    	if (vis[i^tot]==1) { printf("%d %d\n",i,cnt[i^tot]); return 0; }
    return 0;
}