Trie 学习笔记

模板及讲解

字典树

字典树是前缀树,支持$insert(s)$和$query(s)$操作
两个函数按照树结构往下走处理即可

维护二进制 (Xor)

poj 3764

给定一棵$n$个点的带权无向树,求树上路径异或和的最大值。

利用 Xor 性质,我们发现路径异或和满足容斥 (即$[l,r]$可由$[1,r],[1, l-1]$得出)
那么我们求根到每个点的异或和$d_i$,然后尝试如何异或出一条路径来
我们发现任意两个$d_i,d_j$的异或和为某条路径的异或和,且不漏解
那么问题转化为求序列$d_i$两两异或最大值。
因为 Xor 常用 Trie 维护,所以我们可以运用 Trie 求这个最大值。将所有$d_i$以二进制形式插入 Trie (高位在上,定一个最大位数,不够在前面补0),边权为二进制位,然后对于每个二进制下的$d_i$在Trie树上走尽量相反的边,因为这样保证异或后大。树上没有最优边那就只能走另一条边。这样下来的路径就是$d_i$与其他$d_j$的最大异或值。$O(n \cdot len)$操作即可,$len$为二进制最大位数。

Codeforces 842D

常见题型

Trie树
1、前缀问题
2、翻转字符串,处理后缀 jzoj 5397bzoj 4567
3、01Trie:Xor问题 CF 842Dpoj 3764
4、回文相关:Bzoj 1524 (多个回文串拼接问题)
Trie图:AC自动机
Fail树bzoj 2938
前缀关系树 (Trie树去除虚节点) bzoj 4567

------ 本文结束 ------