图论+线性基高斯消元与主元：1019T2 / P4151

http://cplusoj.com/d/senior/p/SS231019B

相当于图上选一条链和一堆环

---

考虑dfs生成树。

则链是两条从根出发的链

环是每条返祖边组成的环

所以环和链的异或和可以求出来

---

链的放到线性基里

然后线性基通过高斯消元求主元（贪心思想，主元可以令那一位一定为1。那么就钦定主元为必选，这样一定更优）

高消的过程中也需要对链进行消元

最后用链来查询，丢01trie上维护

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 100010
//#define M
//#define mo
int n, m, i, j, k, T;
int ans, C, MY, dis[N]; 
struct line_kun {int p[100]; void push(int k) {
//		printf("Add %lld\n", k); for(int j = 62; j >= 0; --j)if((k>>j)&1) {if(!p[j]) { p[j]=k; break; }k^=p[j];  }}void xiaoyuan() {
//		for(int j = 62; j >= 0; --j) printf("%lld ", p[j]); printf("\n"); for(int j = 62; j >= 0; --j)if(p[j]) {for(int i = 62; i > j; --i) if((p[i]>>j)&1) p[i]^=p[j]; for(int i = 1; i <= n; ++i) if((dis[i]>>j)&1) dis[i]^=p[j]; }
//		for(int j = 62; j >= 0; --j) printf("%lld ", p[j]); printf("\n"); }pair<int, int> main_Y() {int k = (1ll<<62)-1, ans = 0; for(int j = 62; j >= 0; --j) if(p[j]) k-=(1ll<<j), ans^=p[j]; return {k, ans}; }
}J; 
struct Trie_tree {int tot = 1, son[N * 60][2] ; int que_max(int x) {
//		printf("Que_mx : %lld\n", x); int u = 1, i, k, ans=0; for(i = 62; i>=0; --i) {k = (x>>i)&1ll; if(son[u][k^1]) u=son[u][k^1], ans|=((k^1)<<i); else u=son[u][k], ans|=(k<<i); }
//		printf("\t We get %lld\n", ans); return ans; }void add(int x) {int u = 1, i, k; for(i = 62; i >= 0; --i) {k = (x>>i)&1ll; if(!son[u][k]) son[u][k] = ++tot; u = son[u][k]; }}
}Trie;
struct node {int y, z; 
};
int u, v, w; 
pair<int, int>p; 
vector<node>G[N]; void dfs(int x, int fa) {for(auto t : G[x]) {int y = t.y, z = t.z; 
//		if(t.y == fa) continue; if(dis[y] == -1) {dis[y] = dis[x] ^ z; dfs(y, x); }else J.push(dis[x] ^ dis[y] ^ z); }
}signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
//	freopen("path.in", "r", stdin);
//	freopen("path.out", "w", stdout);
	T=read();
//	while(T--) {
//
//	}n = read(); m = read(); for(i=1; i<=m; ++i) {u = read(); v = read(); w = read(); G[u].pb({v, w}); G[v].pb({u, w}); }memset(dis, -1, sizeof(dis)); dis[1]=0; dfs(1, 0); 
//	for(i=1; i<=n; ++i) printf("%lld ", dis[i]); printf("\n"); J.xiaoyuan(); p = J.main_Y(); MY = p.first; C = p.second; 
//	cout<<(bitset<100>)(MY)<<endl; 
//	for(i=1; i<=n; ++i) dis[i]&=MY; 
//	printf("# %lld %lld %lld\n", MY, C, k); k=C-(MY&C); C&=MY; 
//	printf("# %lld %lld %lld\n", MY, C, k); 
//	for(i=1; i<=n; ++i) printf("%lld ", dis[i]); printf("\n"); Trie.add(0); for(i=1; i<=n; ++i) {if(i==1) Trie.add(dis[i]); if(i==n)  ans = max(ans, dis[i]^Trie.que_max(dis[i]^C)^C); }printf("%lld", ans^k); return 0;
}