建站网站那个好,做网站推广那家好,示范校建设信息化成果网站,google网站推广http://cplusoj.com/d/senior/p/SS231019B
相当于图上选一条链和一堆环 考虑dfs生成树。
则链是两条从根出发的链
环是每条返祖边组成的环
所以环和链的异或和可以求出来 链的放到线性基里
然后线性基通过高斯消元求主元#xff08;贪心思想#xff0c;主元可以令那一位…http://cplusoj.com/d/senior/p/SS231019B
相当于图上选一条链和一堆环 考虑dfs生成树。
则链是两条从根出发的链
环是每条返祖边组成的环
所以环和链的异或和可以求出来 链的放到线性基里
然后线性基通过高斯消元求主元贪心思想主元可以令那一位一定为1。那么就钦定主元为必选这样一定更优
高消的过程中也需要对链进行消元
最后用链来查询丢01trie上维护
#includebits/stdc.h
using namespace std;
#define int long long
inline int read(){int x0,f1;char chgetchar(); while(ch0||
ch9){if(ch-)f-1;chgetchar();}while(ch0ch9){
x(x1)(x3)(ch^48);chgetchar();}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((kj)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); }pairint, int main_Y() {int k (1ll62)-1, ans 0; for(int j 62; j 0; --j) if(p[j]) k-(1llj), 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, ans0; for(i 62; i0; --i) {k (xi)1ll; if(son[u][k^1]) uson[u][k^1], ans|((k^1)i); else uson[u][k], ans|(ki); }
// 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 (xi)1ll; if(!son[u][k]) son[u][k] tot; u son[u][k]; }}
}Trie;
struct node {int y, z;
};
int u, v, w;
pairint, intp;
vectornodeG[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);Tread();
// while(T--) {
//
// }n read(); m read(); for(i1; im; 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(i1; in; i) printf(%lld , dis[i]); printf(\n); J.xiaoyuan(); p J.main_Y(); MY p.first; C p.second;
// cout(bitset100)(MY)endl;
// for(i1; in; i) dis[i]MY;
// printf(# %lld %lld %lld\n, MY, C, k); kC-(MYC); CMY;
// printf(# %lld %lld %lld\n, MY, C, k);
// for(i1; in; i) printf(%lld , dis[i]); printf(\n); Trie.add(0); for(i1; in; i) {if(i1) Trie.add(dis[i]); if(in) ans max(ans, dis[i]^Trie.que_max(dis[i]^C)^C); }printf(%lld, ans^k); return 0;
}
