[POJ 3764] The xor-longest Path

时间:2023-01-12 00:11:28

Description

多组数据

给你一颗树,

然后求一条最长异或路径,

异或路径长度定义为两点间简单路径上所有边权的异或和。

Solution

首先 dfs 一遍,求出所有的点到根节点(随便选一个)的边权的异或和,用 D 数组来存下。

不难发现,树上 x 到 y 的路径上所有边权的 xor 结果就等于 D[x] xor D[y]。这是因为根据 xor 的性质 (a xor a = 0),“ x 到根 ” 和 “ y 到根 ”这两条路径重叠的部分恰好抵消掉。

所以,问题就变成了从 D[1]~D[N] 这 N 个数中选出两个,xor 的结果最大。

可以用 Trie 树来快速求解。

upd:wa了不下十次数组开大点就能A..  Trie的空间是玄学=.=

Code

#include<cstdio>
#include<cstring>
#include<iostream>
#define N 200015
#define int long long
using namespace std;

];
],d[N<<];
int n,cnt,tot,maxn;

struct Edge{
    int to,nxt,dis;
}edge[N<<];

struct Trie{
    int zero,one;
}trie[N<<];

void add(int x,int y,int z){
    edge[++cnt].to=y;
    edge[cnt].nxt=head[x];
    edge[cnt].dis=z;
    head[x]=cnt;
}

void clear(){
    tot=maxn=;
    memset(d,,sizeof d);
    memset(vis,,sizeof vis);
    memset(head,,sizeof head);
    memset(edge,,sizeof edge);
    memset(trie,,sizeof trie);
}

void dfs(int now){
    vis[now]=;
    for(int i=head[now];i;i=edge[i].nxt){
        int to=edge[i].to;
        if(vis[to]) continue;
        d[to]=d[now]^edge[i].dis;
        dfs(to);
    }
}

void insert(int x){
    ;
    ;~i;i--){
        <<i)){
            if(!trie[now].one) trie[now].one=++tot;
            now=trie[now].one;
        }
        else{
            if(!trie[now].zero) trie[now].zero=++tot;
            now=trie[now].zero;
        }
    }
}

int query(int x){
    ,sum=;
    ;~i;i--){
        <<i));
        if(k){
            <<i,now=trie[now].one;
            else now=trie[now].zero;
        }
        else{
            <<i,now=trie[now].zero;
            else now=trie[now].one;
        }
    }
    return sum;
}

signed main(){
    while((scanf("%lld",&n))!=EOF){
        clear();
        ;i<n;i++){
            scanf("%lld%lld%lld",&x,&y,&z);
            add(x+,y+,z);add(y+,x+,z);
        }
        dfs();
        ;i<=n;i++)
            maxn=max(maxn,query(d[i])),insert(d[i]);
        printf("%lld\n",maxn);
    }
    ;
}

[POJ 3764] The xor-longest Path的更多相关文章

  1. 【POJ 3764】 The xor-longest path

    [题目链接] http://poj.org/problem?id=3764 [算法] 首先,我们用Si表示从节点i到根的路径边权异或和 那么,根据异或的性质,我们知道节点u和节点v路径上的边权异或和就 ...

  2. poj3764 The XOR Longest Path【dfs】【Trie树】

    The xor-longest Path Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 10038   Accepted:  ...

  3. 【POJ 3764】The Xor-longest Path

    题目 给定一个\(n\)个点的带权无根树,求树上异或和最大的一条路径. \(n\le 10^5\) 分析 一个简单的例子 相信大家都做过这题: 给定一个\(n\)个点的带权无根树,有\(m\)个询问, ...

  4. 题解 bzoj1954【Pku3764 The xor – longest Path】

    做该题之前,至少要先会做这道题. 记 \(d[u]\) 表示 \(1\) 到 \(u\) 简单路径的异或和,该数组可以通过一次遍历求得. \(~\) 考虑 \(u\) 到 \(v\) 简单路径的异或和 ...

  5. poj 3764 The xor-longest Path&lpar;字典树&rpar;

    题目链接:poj 3764 The xor-longest Path 题目大意:给定一棵树,每条边上有一个权值.找出一条路径,使得路径上权值的亦或和最大. 解题思路:dfs一遍,预处理出每一个节点到根 ...

  6. Solve Longest Path Problem in linear time

    We know that the longest path problem for general case belongs to the NP-hard category, so there is ...

  7. Why longest path problem doesn&&num;39&semi;t have optimal substructure&quest;

    We all know that the shortest path problem has optimal substructure. The reasoning is like below: Su ...

  8. ACM学习历程—POJ 3764 The xor-longest Path(xor &amp&semi;&amp&semi; 字典树 &amp&semi;&amp&semi; 贪心)

    题目链接:http://poj.org/problem?id=3764 题目大意是在树上求一条路径,使得xor和最大. 由于是在树上,所以两个结点之间应有唯一路径. 而xor(u, v) = xor( ...

  9. Poj 3764 The xor-longest Path&lpar;Trie树&plus;xor&plus;贪心&rpar;

    The xor-longest Path Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 6455 Accepted: 1392 ...

  10. poj 3764 The xor-longest Path &lpar;01 Trie)

    链接:http://poj.org/problem?id=3764 题面: The xor-longest Path Time Limit: 2000MS   Memory Limit: 65536K ...

随机推荐

  1. 初次了解的Java多线程

    0.1熟悉多线程 多线程(英语:multithreading),是指从软件或者硬件上实现多个线程并发执行的技术.具有多线程能力的计算机因有硬件支持而能够在同一时间执行多于一个线程,进而提升整体处理性能 ...

  2. 设计模式之美:Type Object(类型对象)

    索引 意图 结构 参与者 适用性 效果 相关模式 实现 实现方式(一):Type Object 的经典介绍. 实现方式(二):Type Object 在游戏设计中的使用. 意图 允许在运行时动态灵活的 ...

  3. android 获取本机SMI卡号码

    //获取手机号码 TelephonyManager tm = (TelephonyManager)this.getSystemService(Context.TELEPHONY_SERVICE); S ...

  4. my-Life项目开发流程

    一:新建java web项目  (懂得使用gradle哦!) 1.http://www.cnblogs.com/xylle/p/5234380.html 2.新建项目后,然后新建module, 如果甲 ...

  5. Java遇见HTML——JSP篇之JSP指令与动作元素

    一.include指令(如:<%@include file="..."%> ) 示例: Date.jsp <%@page import="java.te ...

  6. objective-c底层&colon; runtime机制

    runtime是oc的真面目.oc底层的一套c语言API. unsigned int count; //获取属性列表 objc_property_t *propertyList = class_cop ...

  7. 我的android学习经历14

    LinearLayout线性布局中gravity和Layout_gravity的解释 这两个都是说明对齐方式的.‘ gravity说明的是子控件的对齐方式,比如把gravity写在LinearLayo ...

  8. Git 钩子

    1. 概念概述 1.1. 安装钩子 1.2. 脚本语言 1.3. 钩子的作用域 2. 本地钩子 2.1. 预提交钩子 Pre-Commit 2.2. 准备提交信息钩子 Prepare Commit M ...

  9. TreeView中节点勾选设置

    本文转载:http://www.cnblogs.com/luxiaoxun/p/3288003.html 很不错的文章:http://www.cnblogs.com/allen0118/archive ...

  10. rpc的学习

    rpc(Remote process call 即远程过程调用)是一种请求-相应的协议, 主要使用于C/S架构中,使得分布式系统成为可能.由客户端发起请求,服务端调用各种参数处理请求,当服务器在处理请 ...