哈尔科夫机车厂最长异或路径研究进展顺利

男娘i 2021-11-17 14:16 127阅读 0赞

# The XOR-longest Path #

[*题面1*][1]

[*题面2*][2]

[*题面3*][3]

这么多OJ都有这道题,说明这是一道经典题呼.

## 题目分析 ##

一棵带权树,求树上任意两点间最长的异或路径.

树上任意两点之间的距离,从\\(LCA\\)算法中我们可以得知可以这样求:

> \\(dis\_\{ij\}\\)=\\(depth\_i\\)\+\\(depth\_j\\)\-\\(2\\)\*\\(depth\_\{LCA\_\{ij\}\}\\)

什么是异或呢,简单地说,两数相同则为0,不同则为1.

所以说有如下性质:

> \\(a\\) \\(xor\\) \\(a\\)=\\(0\\)

这条性质在这道题里尤其重要.

再联想到上面的树上两点距离公式,同志们可以得出树上两点间的异或值的求法,如下图:

![配图1.png][1.png]

红两个红色结点的LCA为蓝色结点,它们之间的异或值也就是黄色的路径上所有边权的异或值.

再结合上面的树上两点距离公式,我们现在需要做的是消去蓝色结点到根结点的异或值.

根据上面讲到的异或的性质,两个相等的数的异或值等于0,所以说把两个红色结点到根结点的异或值异或起来,就可以得到黄色路径上的异或值.如下图:

![配图2.png][2.png]

可以看到,根节点到蓝色结点的异或值被计算了两次,于是就被消为了\\(0\\),对之后的异或运算没有影响.

所以说,这道题就转化成了求出树上任意一点到根结点的异或值,再求出任意两个异或值中的最大值.

为了方便计算,我们把边权拆成二进制的数.这样的话根据异或的运算法则,两个数不一样就为\\(1\\),一样就为\\(0\\),我们尽量选择不一样的数.为了满足最大值,我们从高位开始.

朴素的思想就是暴力枚举每个结点了.

再仔细想一想,发现这时候的本质无非就是要在一堆二进制数里找出与这个二进制数尽量每一位都不相等的数中最长的数.

我们把不同的位数视为两个数的前缀,然后就可以想到用Trie实现找前缀了.

同志们可以把每个结点到根结点的异或值存在Trie里,不足31位的用0补位.

因为高位的数一定比低位大,同志们每次都尽量选择与原串不同的高位,满足贪心策略.

## 代码 ##

#include "cstdio" #include "algorithm" #include "cstring" #include "iostream" #define ll long long #define debug(x) printf("debug:%lld\n",x) using namespace std; struct edge { ll to,val,next; }e[10000010]; ll n,g,tot=1,ans,size; ll trie[1000010][2],TwoBit[33],head[1000010],xor_[1000010]; bool flag[10000010]; inline void EdgeAdd(ll,ll,ll); inline void insert(); inline ll search(); inline void dfs(ll); signed main(void) { memset(head,-1,sizeof(head)); scanf("%lld",&n); for(ll _=1;_<=n-1;_++) { ll a,b,v; scanf("%lld%lld%lld",&a,&b,&v); EdgeAdd(a,b,v); EdgeAdd(b,a,v); } dfs(1); for(ll _=1;_<=n;_++) { memset(TwoBit,0,sizeof(TwoBit)); g=-1; ll v=xor_[_]; while(v)//拆二进制 { TwoBit[++g]=v&1; v>>=1; } insert(); } for(ll _=1;_<=n;_++) { memset(TwoBit,0,sizeof(TwoBit)); g=-1; ll v=xor_[_]; while(v)//拆二进制 { TwoBit[++g]=v&1; v>>=1; } ans=max(ans,search()); } printf("%lld\n",ans); return 0; } inline void EdgeAdd(ll from,ll to,ll val) { e[++size].to=to; e[size].val=val; e[size].next=head[from]; head[from]=size; } inline void dfs(ll from)//用dfs求出到根结点的异或值 { flag[from]=true; for(ll _=head[from];_!=-1;_=e[_].next) { ll to=e[_].to; ll val=e[_].val; if(flag[to]==true)//不能往回走啊 { continue; } else { xor_[to]=xor_[from]^val;//累加异或值 dfs(to); } } } inline void insert() { ll p=1; for(ll _=31;_>=0;_--)//从高位开始存 { ll num=TwoBit[_]; if(trie[p][num]==0) { trie[p][num]=++tot; } p=trie[p][num]; } } inline ll search() { ll p=1,cnt=0; for(ll _=31;_>=0;_--)//从高位开始扫 { ll num=TwoBit[_]; if(trie[p][1-num]!=0)//尽量选择与高位不同的 { cnt+=(1<<_); p=trie[p][1-num]; } else { p=trie[p][num]; } } return cnt; }

转载于:https://www.cnblogs.com/Lemir3/p/11174480.html

[1]: https://loj.ac/problem/10056
[2]: https://www.luogu.org/problemnew/show/P4551
[3]: http://poj.org/problem?id=3764
[1.png]: https://i.loli.net/2019/07/12/5d27e67b7397e79066.png
[2.png]: https://i.loli.net/2019/07/12/5d27e8848809458766.png