【BZOJ1954】The xor-longest Path


题意

求树上最大的xor路径。

分析

对于树上的路径 \(x->y\) ,我们可以由 xor 的可逆运算得到 \(x->y\) xor结果就是 \(x->1\) xor \(1->y\) 

于是我们预处理所有 \(1->x\) xor 结果,记为 \(f[x]\)。

那么剩下的问题就是找 \(x\) \(y\) ,使得 \(f[x]\; xor \; f[y]\) 最大。

这个就是一个经典的字典树问题了。

把所有的\(f[x]\)拆成二进制,高位在前低位在后看作字符串,插入Trie。

对于每一个数\(f[x]\),从高位到低位在Trie上跑,贪心的尽量向每一位 xor 结果为\(1\)的子树上跑。

时间复杂度\(\mathcal{O}(n*log_2(max{a_i}))\)。

 

You may also like

LEAVE A COMMENT

Statistics

  • 0
  • 8,096

Categories

Archive

Comments