POJ 3764 – The xor-longest Path

题目链接:POJ – 3764 

记一个点$u$到根节点的路径异或和为$f(u)$,那么$u$到$v$的路径异或和为$f(u) \oplus f(v)$,因为如果我们用$d(u, v)$来表示$u$到$v$的路径异或和,那么

$$  \begin{aligned} d(u, v)  = & d(u, {\rm lca}(u, v) ) \oplus d(v, {\rm lca}(u, v) ) \\ = & d(u, {\rm lca}(u, v) ) \oplus d(v, {\rm lca}(u, v) ) \oplus d({\rm lca}(u, v), {\rm root}) \oplus d({\rm lca}(u, v),{\rm root}) \\ = & f(u) \oplus f(v)  \end{aligned}  $$

所以我们首先需要一次DFS预处理出所有$f(x)$的值,然后在序列$f(x)$中找两个数异或和最大,这又回到了AcWing 143(参考我的上一篇文章),使用字典树求解。

在读题的时候发现题目没有说明哪个点是根,其实随便哪个点作根都不影响任意两点之间路径的异或和。

吐槽:邻接表卡vector,真是sb。

 

说点什么

avatar
50
  Subscribe  
提醒