【题目描述】
原题来自:POJ 3764

给定一棵 n 个点的带权树,求树上最长的异或和路径。

【输入】
第一行一个整数 n,接下来 n−1 行每行三个整数 u,v,w,表示 u,v 之间有一条长度为 w 的边。

【输出】
输出一行一个整数,表示答案。

【输入样例】
4
1 2 3
2 3 4
2 4 6
【输出样例】
7
【提示】
样例解释

最长的异或和路径是 1→2→3 ,它的长度是 3⨁4=7。

注意:结点下标从 1 开始到 N。

注:x⨁y 表示 x 与 y 按位异或。

原理介绍

xor_disx=xor_dis0^xor_dis0

代码

#include <iostream>
#include <cstdio>
using namespace std;


const int N=1e6+128;
namespace G
{
    struct Edge
    {
        int to;
        int next;
        unsigned int val;
    }   egde[N];
    int deg=0;

    int head[N];

    inline void add_edge(int from,int to,unsigned  int val)
    {
        egde[++deg].next=head[from];
        egde[deg].to=to;
        egde[deg].val=val;

        head[from]=deg;
    }

    unsigned int dis[N];    // 用来表示 1 节点到 n 节点 xor路径

    void dfs(int x,unsigned int val)
    {
        dis[x]=val;
        for(int i=head[x]; i!=0; i=egde[i].next)
            dfs(egde[i].to,val^egde[i].val);
    }
}


namespace trie
{
    struct Node
    {
        Node * next[2];
    }   trie[N];
    int m;

    inline Node * NEW()
    {
        return &trie[m++];
    }

    inline int getbit(unsigned int val,int addr)
    {
        return (val>>(addr-1))&1;
    }

    void insert(unsigned int val,int n,Node * trie_node)
    {
        if(n==0)
            return ;
        int c=getbit(val,n);
        if(trie_node->next[c]==NULL)
            trie_node->next[c]=NEW();
        insert(val,n-1,trie_node->next[c]);
    }

    void FindMaxVal(unsigned int &buffer_num,int n,Node * trie_node)
    {
        if(n==0)
            return ;
        int c=getbit(buffer_num,n);
        if(trie_node->next[c^1]!=NULL) //c^1 该位为1
        {
            buffer_num|=1<<(n-1);
            FindMaxVal(buffer_num,n-1,trie_node->next[c^1]);
        }   else    {   //  为 0
            buffer_num^=c<<(n-1);   //c=c^c==0
            FindMaxVal(buffer_num,n-1,trie_node->next[c]);
        }
    }

}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1; i<n; i++) //n个点只有 n-1条边
    {
        int u,v;
        unsigned w;
        scanf(" %d %d %u",&u,&v,&w);
        G::add_edge(u,v,w);
    }
    G::dfs(1,0);

    trie::NEW();

    for(int i=1;i<=n;i++)
        trie::insert(G::dis[i],32,&trie::trie[0]);

    unsigned int maxn=0;

    //这里有个重要结论 xor_disx=xor_dis0^xor_dis0;

    for(int i=1;i<=n;i++)
    {
        unsigned int t=G::dis[i];
        trie::FindMaxVal(t,32,&trie::trie[0]);
        maxn=max(maxn,t);
    }

    printf("%u",maxn);
}

Last modification:April 15th, 2021 at 12:00 pm