如何进行网页设计和网站制作,高端网站建设公司注意什么,省建设信息中心查询,凤蝶直播最长异或路径
题目描述
给定一棵 n n n 个点的带权树#xff0c;结点下标从 1 1 1 开始到 n n n。寻找树中找两个结点#xff0c;求最长的异或路径。
异或路径指的是指两个结点之间唯一路径上的所有边权的异或。
输入格式
第一行一个整数 n n n#xff0c;表示点数…最长异或路径
题目描述
给定一棵 n n n 个点的带权树结点下标从 1 1 1 开始到 n n n。寻找树中找两个结点求最长的异或路径。
异或路径指的是指两个结点之间唯一路径上的所有边权的异或。
输入格式
第一行一个整数 n n n表示点数。
接下来 n − 1 n-1 n−1 行给出 u , v , w u,v,w u,v,w 分别表示树上的 u u u 点和 v v v 点有连边边的权值是 w w w。
输出格式
一行一个整数表示答案。
样例 #1
样例输入 #1
4
1 2 3
2 3 4
2 4 6样例输出 #1
7提示
最长异或序列是 1 , 2 , 3 1,2,3 1,2,3答案是 7 3 ⊕ 4 73\oplus 4 73⊕4。
数据范围 1 ≤ n ≤ 100000 ; 0 u , v ≤ n ; 0 ≤ w 2 31 1\le n \le 100000;0 u,v \le n;0 \le w 2^{31} 1≤n≤100000;0u,v≤n;0≤w231。 插入
代码
//每条路径 a,b 的 xor 和转化成 “(a 到根的 xor 和) xor (b 到根的 xor 和)”
#includebits/stdc.h
using namespace std;
struct node{int left0,right0;
}root;
vectornode trie;
vectorint a[100001],b[100001];//连接情况记录在a数组权重情况记录在b数组
int yihuo[100005];//搜索异或值的结果
//通过dfs搜出所有节点到根节点的异或值
void dfs(int x,int y){//x代表节点y代表当前的异或值是多少for(int i0;ia[x].size();i){yihuo[a[x][i]]y^b[x][i];//当前异或值异或连接到的节点的权重dfs(a[x][i],yihuo[a[x][i]]);//继续往下搜}
}
//生成01字典树
void build(int x){//记录各个节点的左右节点编号这里默认左节点储存0右节点储存1int fa0,len;//每次重新输入一个异或值生成01树的时候fa都要重新置0for(int i(130);i0;i1){//边的权值最大为2的31次方说明边权的异或最大值也是lentrie.size();//树的节点if(xi){//当前位为1遍历右边的if(trie[fa].right0){//没有右节点trie[fa].rightlen;// coutfa right lenendl;trie.push_back(root);//把空节点push_back进去falen;//下一次的父节点为当前的节点编号}else fatrie[fa].right; }else{//当前位为0,遍历左边的if(trie[fa].left0){//没有左节点trie[fa].leftlen;//给左节点编号// coutfa left lenendl;trie.push_back(root);falen;}else fatrie[fa].left;}}
}
int jisuan(int x){int ans0,fa0;coutxendl;for(int i(130);i0;i1){//i的初始值为130是因为边的权值最大为2的31次方if(xi){//当前位为1由于是要求最长的异或路径所以需要遍历左边的0才能使得当前值为1if(trie[fa].left){ansi;// coutleft ans trie[fa].leftendl;fatrie[fa].left;}else fatrie[fa].right;}else{//当前位为0由于是要求最长的异或路径所以需要遍历右边的1才能使得当前值为1if(trie[fa].right){ansi;// coutright ans trie[fa].rightendl;fatrie[fa].right;}else fatrie[fa].left;}}// coutx ans;return ans;
}
void lesson1(){int n,x,y,z,ans0;cinn;for(int i1;in;i){cinxyz;a[x].push_back(y);b[x].push_back(z);}dfs(1,0);trie.push_back(root);//0号节点其左节点为0号节点右节点为0号节点for(int i1;in;i){build(yihuo[i]);// cinx;// coutxendl;// build(x); }for(int i1;in;i){ansmax(ans,jisuan(yihuo[i]));}coutansendl; // for(int i1;in;i){// couti:;// for(int j0;ja[i].size();j)couta[i][j],b[i][j] ;// coutendl;// }// for(int i1;in;i)coutyihuo[i] ;//根据题目样例得到0 3 7 5// for(int i0;itrie.size();i){// couti:trie[i].left,trie[i].rightendl;// }
}
int main(){lesson1();return 0;
}
