### [题目链接](https://www.luogu.com.cn/problem/P4151) 对于任意一个环，有两条路径可以走，很显然这两条路径的权值的异或和等于整个环的异或和。 我们发现从 $1\to n$ 的任意一条路径都可以转化为从 $1$ 到 $n$ 的某一条路径再在某几个环上走另一边。 所以答案就是从 $1\to n$ 的任意一条路径的权值异或上若干个环的权值。用线性基可维护异或最大值。 再考虑如何求出每个环的异或和，如果我们建出 DFS 树，只有树边和返祖边，一条返祖边恰好对应一个环，我们就可以轻松地求出异或和了。 如果两个环相交形成一个大环，我们发现也可以通过这两个环异或得到这个大环的异或和，就可以表示出所有的环了！ ### CODE ```cpp #include <bits/stdc++.h> #define int long long using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=5e4+10; int n, m, num[N], del[N], vis[N]; vector<pair<int, int> > e[N]; void insert(int x) { for (int i=63; i>=0; i--) { if (!(x>>i&1)) continue; if (num[i]) x^=num[i]; else return num[i]=x, void(); } } int query(int x) { int res=x; for (int i=63; i>=0; i--) if ((res^num[i])>res) res^=num[i]; return res; } void dfs(int x, int res) { del[x]=res, vis[x]=1; for (auto [y, z]:e[x]) { if (!vis[y]) dfs(y, res^z); else insert(res^z^del[y]); } } signed main() { n=read(), m=read(); for (int i=1; i<=m; i++){ int a=read(), b=read(), c=read(); e[a].push_back({b, c}); e[b].push_back({a, c}); } dfs(1, 0); printf("%lld\n", query(del[n])); return 0; } ``` Loading... ### [题目链接](https://www.luogu.com.cn/problem/P4151) 对于任意一个环，有两条路径可以走，很显然这两条路径的权值的异或和等于整个环的异或和。 我们发现从 $1\to n$ 的任意一条路径都可以转化为从 $1$ 到 $n$ 的某一条路径再在某几个环上走另一边。 所以答案就是从 $1\to n$ 的任意一条路径的权值异或上若干个环的权值。用线性基可维护异或最大值。 再考虑如何求出每个环的异或和，如果我们建出 DFS 树，只有树边和返祖边，一条返祖边恰好对应一个环，我们就可以轻松地求出异或和了。 如果两个环相交形成一个大环，我们发现也可以通过这两个环异或得到这个大环的异或和，就可以表示出所有的环了！ ### CODE ```cpp #include <bits/stdc++.h> #define int long long using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=5e4+10; int n, m, num[N], del[N], vis[N]; vector<pair<int, int> > e[N]; void insert(int x) { for (int i=63; i>=0; i--) { if (!(x>>i&1)) continue; if (num[i]) x^=num[i]; else return num[i]=x, void(); } } int query(int x) { int res=x; for (int i=63; i>=0; i--) if ((res^num[i])>res) res^=num[i]; return res; } void dfs(int x, int res) { del[x]=res, vis[x]=1; for (auto [y, z]:e[x]) { if (!vis[y]) dfs(y, res^z); else insert(res^z^del[y]); } } signed main() { n=read(), m=read(); for (int i=1; i<=m; i++){ int a=read(), b=read(), c=read(); e[a].push_back({b, c}); e[b].push_back({a, c}); } dfs(1, 0); printf("%lld\n", query(del[n])); return 0; } ``` 最后修改：2025 年 07 月 02 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏