加载中…POJ 3764 字典树应用 异或运算
(2011-05-04 22:38:57)
标签：
poj3764字典树应用异或运算it |
分类： 图论 |
题目描述：
给你一棵树，n个节点（n = 100000），n-1条边每条边i都有一个权值wi。
定义任意两点间的权值为：
这两点间的路径上的所有边的值的异或。
比如a点和b点间有i，j，k三条边，那么ab两点间的权值为：wi^wj^wk
求这个最大的权值。
解题报告：
转自：http://blog.csdn.net/zhaofukai/archive/2011/03/12/6242612.aspx
这道题要求最长的异或路径：就是在树中找两个节点，两个节点间有唯一路径（因为是树），把路径不断做异或，异或完后求最大的。数据是10万，O（n2）算法超时。我们知道异或有这样的性质：a^b = (a^c)^(b^c)，这样就可以考虑找出a与b公共的c，实际上就是求出从根节点到每个节点的异或值，这样任意两个点做异或，即是他们之间的异或路径（相同部分异或抵消了）。可以dfs遍历一遍，我在这里就花了很多时间，用邻接表表示树用的很少，很不熟练。然后可以用字典树来储存每个节点的值，问题又转化成求这n个数中，任意两个数做异或，求最大值，用字典树的复杂度为O（n*31），前面dfs复杂度为O(n)，所以效率还是比较好的。程序中注意优化，否则TLE，例如：u、v节点，u可能比v大，我们就交换它们来建邻接点，而不必建两次。
喜欢
0
赠金笔