P4551 最长异或路径 - 服务器托管|北京服务器租用|机房托管租用|IDC托管租用|机房机柜带宽租用-价格及费用咨询

最长异或路径

题目描述

给定一棵

$n$ 个点的带权树，结点下标从

$1$ 开始到

$n$ 。寻找树中找两个结点，求最长的异或路径。

异或路径指的是指两个结点之间唯一路径上的所有边权的异或。

输入格式

第一行一个整数

$n$ ，表示点数。

接下来

−

n-1

$n - 1$ 行，给出

u,v,w

$u, v, w$ ，分别表示树上的

服务器托管网 $u$ 点和

$v$ 点有连边，边的权值是

$w$ 。

输出格式

一行，一个整数表示答案。

样例 #1

样例输入 #1

样例输出 #1

提示

最长异或序列是

,服务器托管网

1,2,3

$1, 2, 3$ ，答案是

⊕

7=3oplus 4

$7 = 3 \oplus 4$ 。

数据范围

≤

100000

;

$1 \leq n \leq 100000; 0 u, v \leq n; 0 \leq w 2^{31}$ 。
插入

代码：

//每条路径  的 xor 和转化成 “(a 到根的 xor 和) xor (b 到根的 xor 和)”
#include
using namespace std;
struct node{
    int left=0,right=0;
}root;
vectornode> trie;
vectorint> a[100001],b[100001];//连接情况记录在a数组，权重情况记录在b数组
int yihuo[100005];//搜索异或值的结果
//通过dfs搜出所有节点到根节点的异或值
void dfs(int x,int y){//x代表节点，y代表当前的异或值是多少
    for(int i=0;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，右节点储存1
    int fa=0,len;//每次重新输入一个异或值生成01树的时候fa都要重新置0
    for(int i=(130);i>0;i>>=1){//边的权值最大为2的31次方，说明边权的异或最大值也是
        len=trie.size();//树的节点
        if(x&i){//当前位为1，遍历右边的
            if(trie[fa].right==0){//没有右节点
                trie[fa].right=len;
                // cout
                trie.push_back(root);//把空节点push_back进去
                fa=len;//下一次的父节点为当前的节点编号
            }else fa=trie[fa].right;    
        }else{//当前位为0,遍历左边的
            if(trie[fa].left==0){//没有左节点
                trie[fa].left=len;//给左节点编号
                // cout
                trie.push_back(root);
                fa=len;
            }else fa=trie[fa].left;
        }
    }
}
int jisuan(int x){
    int ans=0,fa=0;
    coutxendl;
    for(int i=(130);i>0;i>>=1){//i的初始值为1
        if(x&i){//当前位为1，由于是要求最长的异或路径，所以需要遍历左边的0，才能使得当前值为1
            if(trie[fa].left){
                ans+=i;
                // cout
                fa=trie[fa].left;
            }
            else fa=trie[fa].right;
        }
        else{//当前位为0，由于是要求最长的异或路径，所以需要遍历右边的1，才能使得当前值为1
            if(trie[fa].right){
                ans+=i;
                // cout
                fa=trie[fa].right;
            }
            else fa=trie[fa].left;
        }
    }
    // cout
    return ans;
}
void lesson1(){
    int n,x,y,z,ans=0;
    cin>>n;
    for(int i=1;in;i++){
        cin>>x>>y>>z;
        a[x].push_back(y);
        b[x].push_back(z);
    }
    dfs(1,0);
    trie.push_back(root);//0号节点，其左节点为0号节点，右节点为0号节点
    for(int i=1;in;i++){
        build(yihuo[i]);
        // cin>>x;
        // cout
        // build(x);       
    }
    for(int i=1;in;i++){
        ans=max(ans,jisuan(yihuo[i]));
    }
    coutansendl;   
    // for(int i=1;i
    //     cout
    //     for(int j=0;j
    //     cout
    // }
    // for(int i=1;i
    // for(int i=0;i
    //     cout
    // }
}
int main(){
    lesson1();
    return 0;
}

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: ChatGPT高效提问—prompt基础

ChatGPT高效提问—prompt基础设计一个好的prompt对于获取理想的生成结果至关重要。通过选择合适的关键词、提供明确的上下文、设置特定的约束条件，可以引导模型生成符合预期的回复。例如，在对话中，可以使用明确的问题或陈述引导模型生成相关、具体的回…