有单支log的解法
查看原帖
有单支log的解法
61528
_cyxh_楼主2021/8/27 21:32

将两点间路径的亦或和转化为两点赋值的亦或后,不要急着求出每个子树的最大路径,而是先把全局最大路径先拉出来,这样再分类讨论就可以让每个节点的访问次数达到O(1),于是就只剩下01trie的log
这主要是因为,想知道树上某个联通块的最大路径,只需把联通块中所有点的赋值全部加入01trie,再对联通块中每个点的赋值分别在这个01trie中查询亦或最大,并取max即可

2021/8/27 21:32
加载中...