3 solutions
-
3
有彩蛋(仅限认识孙煜卿的人)
前置
如果你上一道题(校内)(校外)没有做对就不要做这道题,因为会用到那道题的思路
题意
找出这个树中最大的异或路径长度
异或路径长度就是指 x到y 的每个路径权值互相异或的值
思路2
暴力哥,这不用讲了
但是会 TLE
AC 做法:
随便找出一个根节点,树形结构,都是一样的
求出根节点到每一个点的异或路径长度存在dis数组
然后找出dis中的最大异或对
为什么这么做可以呢?
因为 x到y 的异或路径长度等于 root到x^root到y 的
为什么呢?
x^x=0 , 0^x=x
重复的路段可以被抵消
代码
部分代码与上一道题思路一样,看不懂的可以去看这一篇题解的代码注释
#include<bits/stdc++.h> #define N 1000005 using namespace std; int n,ma=0; struct edge { int v,w; }; vector<edge>g[N]; int dis[N]; queue<int>q; void bfs()//找出树根到每个点的异或长度 { q.push(1); while(!q.empty()) { int u=q.front(); q.pop(); for(int i=0;i<g[u].size();i++)//树形结构,无需vis { int v=g[u][i].v; int w=g[u][i].w; dis[v]=dis[u]^w;//注意这里 q.push(v); } } } int trie[N][5]; int word[N]; int tot=0; void insert(int id)//模板++ { bitset<32>s(dis[id]); int u=0; for(int i=31;i>=0;i--) { int x=s[i]; if(!trie[u][x]) trie[u][x]=++tot; u=trie[u][x]; } word[u]=id; } void find(int id)//模板++ { bitset<32>s(dis[id]); int u=0; int j=0; for(int i=31;i>=0;i--) { int x=s[i]; u=trie[u][x]; if(trie[j][!x]) j=trie[j][!x]; else if(trie[j][x]) j=trie[j][x]; } ma=max(ma,dis[word[u]]^dis[word[j]]); } int main() { cin>>n; for(int i=0;i<n-1;i++) { int u,v,w; cin>>u>>v>>w; g[u].push_back({v,w}); } bfs(); for(int i=1;i<=n;i++) { insert(i); } for(int i=1;i<=n;i++) { find(i); } cout<<ma; return 0; }彩蛋
调试代码时候的意外彩蛋
4 1 2 3 2 3 4 2 4 6看看输出结果
#include<bits/stdc++.h> #define N 100005 using namespace std; int n,ma=0; struct edge { int v,w; }; vector<edge>g[N]; int dis[N]; queue<int>q; void bfs() { q.push(1); while(!q.empty()) { int u=q.front(); q.pop(); for(int i=0;i<g[u].size();i++) { int v=g[u][i].v; int w=g[u][i].w; dis[v]=dis[u]+w; q.push(v); } } } int trie[N][5]; int word[N]; int tot=0; void insert(int id) { bitset<32>s(dis[id]); int u=0; for(int i=31;i>=0;i--) { int x=s[i]; if(!trie[u][x]) trie[u][x]=++tot; u=trie[u][x]; } word[u]=id; } void find(int id) { bitset<32>s(dis[id]); int u=0; int j=0; for(int i=31;i>=0;i--) { int x=s[i]; u=trie[u][x]; if(trie[j][!x]) j=trie[j][!x]; else if(trie[j][x]) j=trie[j][x]; } ma=max(ma,dis[word[u]]^dis[word[j]]); } int main() { cin>>n; n-=1; for(int i=0;i<n;i++) { int u,v,w; cin>>u>>v>>w; g[u].push_back({v,w}); } bfs(); for(int i=1;i<=n;i++) cout<<dis[i]<<" "; for(int i=1;i<=n;i++) { insert(i); } for(int i=1;i<=n;i++) { find(i); } cout<<ma; return 0; } -
1
C23zhuanghaojun
LV 6
@ 2024-11-20 13:50:59
#include<bits/stdc++.h> using namespace std; vector<pair<int,int>>g[100005]; int f[100005]; int trie[10000000][2]; int tot,ans; string maxn,str; void dfs(int a,int s){ f[a]=s; int sz=g[a].size(); if(sz==0){ return; } for(int i=0;i<sz;i++){ dfs(g[a][i].first,s^g[a][i].second); } } void ins(string k){ int u=0; int sz=k.size(); for(int i=0;i<sz;i++){ int a=k[i]-'0'; if(trie[u][a]==0){ tot++; trie[u][a]=tot; } u=trie[u][a]; } } void find(string k){ int u=0; int sz=k.size(); maxn=""; for(int i=0;i<sz;i++){ int a=k[i]-'0'; if(a==0){ if(trie[u][1]!=0){ u=trie[u][1]; maxn+="1"; } else{ u=trie[u][0]; maxn+="0"; } } else{ if(trie[u][0]!=0){ u=trie[u][0]; maxn+="1"; } else{ u=trie[u][1]; maxn+="0"; } } } bitset<31> bit(maxn); int sum=bit.to_ullong(); ans=max(sum,ans); } int main(){ int n; cin>>n; for(int i=1;i<n;i++){ int u,v,w; cin>>u>>v>>w; g[u].push_back({v,w}); } dfs(1,0); for(int i=1;i<=n;i++){ bitset<31> bit(f[i]); str=bit.to_string(); ins(str); find(str); } cout<<ans; } -
-3
C23huangyuran
LV 6
@ 2024-11-14 14:01:28
如果你上一题没有思路，就不用在本题浪费时间了。
题意
这个题的题意肥肠有必要写。（tm一堆符号
牢大大牢才看得懂）给你一个图，要你求出这个图中所有路径的最大权值异或和。
也就是说，有一条路径，上面的权值有，，……，那么它的权值异或和就是：
思路
搞笑向
笑死，没有思路。紧急求助zengfj……
A了？
简明扼要版
1.复制上一题代码。
2.在前面加一点点的图论输入。
3.速写bfs。
不play了
首先，我们先看样例啊……
3 /[4] 1—[3]—2 \[6] 4众所周知啊，任何一颗树在改变根节点之后还是一棵树。（
这个都不会吃shit吧）为了写题解我居然专门去找AI，
我真贴心（tiangong万岁）（绝对不是我知道但我不会证明）（以下内容为AI生成）- 树的定义
- 树是一种无向连通图且没有环。在树中，任意两个顶点之间有且仅有一条路径。
- 以不同节点为根的情况分析
- 当我们选择一个节点作为根节点时，对于树中的其他节点，它们与根节点之间的连接关系会形成一种层次结构。
- 假设我们有一棵原始树(T)，节点集为(V)，边集为(E)。
- 当我们选择节点(u\in V)作为根节点时，对于任意节点(v\in V)，从(u)到(v)存在唯一的路径(P_{uv})。
- 现在如果我们选择另一个节点(w\in V)作为根节点，对于任意节点(x\in V)，从(w)到(x)也存在唯一的路径(P_{wx})。
- 因为树本身的无环性和连通性是其固有属性，无论我们选择哪个节点作为根节点，这种无环性和连通性都不会改变。
- 例如，对于节点(a)、(b)、(c)在原始树中(a - b - c)是一条路径，若以(b)为根节点，(a)和(c)分别处于(b)的不同子树中；若以(a)为根节点，(b)和(c)就在(a)的子树结构中，但它们之间的连接关系依然保持，不会出现新的边或者环。
- 结论
- 所以，一棵树不管以哪个节点为根节点，都保持树的结构。
很好，聪明的，你应该已经知道了这个煎蛋的结论，所以这么一串东西只为了证明：我们可以以1作为根节点。
回到上面的图——贴心的我又给你们复制了一份：
3 /[4] 1—[3]—2 \[6] 4我们可以发现，1-3的路径是3^4，1-4的路径是3^6对吧。
然后3-4的结果很好说，4^6嘛。
你看，(3^4)^(3^6)=4^6。（异或基本原理：x^x=0,0^x=x）
so?（
聪明的孩子已经不用看了）大胆猜想，小心求证，发现我们把从1到x的异或路径标为f[x]，那么x到y的异或路径就是f[x]^f[y]。
原理
x和y的最近公共祖先为a，那么a-x为左边一条，a-y为右边一条，那么x-y就把两条连起来，(a-x)^(a-y)。
那么不是最近呢？
他们共有的部分不就会在相互异或中抵掉吗？
而根节点，就是所有节点的公共祖先！（perfect！）
这道题目其实写起来不难，但是思路复杂。
（
一般的孩子也不用继续看了）这个时候，有些纸张就会问了：怎么找根节点到x的路径啊？
bfs啊~
于是你就会做这道题目了。
（这个题目的思路类似于人脑分治，把难题分成一个个部分，分别想到对应的办法，就可以解决了，这样的思路对于所有题目都很有帮助）
好问题，这个东西放在Trie Tree干什么？（毫无关联）
你看，你要找f[x]^f[y]的最大值，那么遍历不就需要？
你这样想，我们现在要把一堆数中最大的a^b给找出来……
很好，这是上一题。（看懂标题那句话了吧~）
代码
因为我是复制上一题的代码的，所以可能有点乱，仅供参考，而且Trie Tree的部分就不予注释了。
//math:x^x=0 ->这是我开始时写的，不是题解注释。 //不过这两句是。 #include<iostream> #include<vector>//一眼图论 #include<queue>//一眼bfs #define N int(4e6) using namespace std; int ans(0); class Trie{ public: int n; int trie[N][2]{}; int word[N]{}; void insert(string); }; Trie a; vector<pair<int,int>>m[N]{};//邻接表 int f[N]{};//表示1-i的路径 int main(){ int n(0); cin>>n; for(int i(1);i<n;i++){//建图 int u(0); int v(0); int w(0); cin>>u>>v>>w; m[u].push_back({v,w}); } queue<int>q; f[1]=0; q.push(1); while(!q.empty()){//bfs int u(q.front()); q.pop(); int len(m[u].size()); for(int i(0);i<len;i++){//不用在意会不会重复 //因为这是树 f[m[u][i].first]=f[u]^m[u][i].second; q.push(m[u][i].first); } } for(int i(1);i<=n;i++){ string x(""); for(int j(1);j<=32;j++) x+='0'+bool(f[i]&(1<<(32-j))); a.insert(x); } cout<<ans; } void Trie::insert(string s){ int u(0); for(auto ch:s){ bool x(ch-'0'); if(!trie[u][x]) trie[u][x]=++n; u=trie[u][x]; } u=0; int f(0); for(int i(0);i<32;i++){ bool x(s[i]-'0'); if(trie[u][!x]){ u=trie[u][!x]; f+=1<<(31-i); } else u=trie[u][x]; } ans=max(ans,f); }-
C23linzixuan
@ 2025-1-16 16:54:06
优质题解，必须好评！
- 树的定义
C23panweiming
LV 8
@ 2024-11-15 18:45:04
- 1
