保姆级教学——字典树-程序员充电站

字典树

字典树的原理是复用前缀信息，所以字典树又叫前缀树。

构建过程

这里只介绍基本的构建框架，因为字典树的能实现的功能很多，所以结点信息种类也很多，不可能把所有的信息都写上，所以只写框架，后续再根据题目自己补充。

假设字符集是a ∼ z \mathrm a\sim\mathrm za∼z共26 \mathrm {26}26个字符最开始字典树有一个根结点1 \mathrm 11，然后这个根结点需要维护26 2626条边( c h a r , v ) (\mathrm {char},\mathrm v)(char,v)，表示这条边对应的字符种类，以及这条边的另一个端点v \mathrm vv。最初26 \mathrm {26}26条边都不存在。

加入字符串

最初我们在树根，设其深度为d e e p \mathrm {deep}deep，根节点的深度为0 \mathrm 00，全局维护一个结点池c n t \mathrm {cnt}cnt，初值为1 \mathrm 11。我们要将字符串s \mathrm ss加入树中：

对于当前字符s d e e p \mathrm {s_{deep}}sdeep，检查当前结点是否存在对应字符的边( s d e e p , v ) \mathrm {(s_{deep},v)}(sdeep,v)；
如果存在，则前往下一个结点v \mathrm vv，重复检查过程；
如果不存在，那么给当前结点建边( s d e e p , c n t + 1 ) \mathrm {(s_{deep},cnt+1)}(sdeep,cnt+1)，然后跳转到下一个结点c n t + 1 \mathrm {cnt+1}cnt+1；
直到访问到字符串最后一位字符。

查询字符串是否存在

最初我们在树根，我们查询字符串s \mathrm ss是否在树中出现过。

对于当前字符s d e e p \mathrm {s_{deep}}sdeep，检查当前结点是否存在对应字符的边( s d e e p , v ) \mathrm {(s_{deep},v)}(sdeep,v)；
如果存在，则前往下一个结点v \mathrm {v}v；
如果不存在，直接报告不存在；
如果访问到最后一个字符仍存在，那么报告存在。

删除字符串

这个具体题目有具体的删除方式，主要是看我们给每个结点定义了怎样的信息，参照之前每个字符串是如何贡献的，删除字符串就是将字符串的贡献取消。

模板1

模版题1

查询某个字符串是否出现，以及是否出现过两次。

需要给每个结点加一些额外信息，即e n d \mathrm{end}end，其中e n d \mathrm {end}end表示当前结点以末尾的形式出现的次数。

#include<bits/stdc++.h>usingnamespacestd;//#pragma GCC optimize(2)#defineintlonglong#defineendl'\n'#definePIIpair<int,int>#defineINF1e18constintM=1e5;constintN=1e4;inttr[50*N+50][27];intEnd[50*N+50];intcnt=1;intexist(string&s){intnext=1;for(inti=0;i<s.size();i++){if(!tr[next][s[i]-'a']){return0;}next=tr[next][s[i]-'a'];}returnEnd[next];}voidadd(string&s){intnext=1;for(inti=0;i<s.size();i++){if(!tr[next][s[i]-'a']){tr[next][s[i]-'a']=++cnt;}next=tr[next][s[i]-'a'];}End[next]++;return;}voidslove(){intn;cin>>n;for(inti=1;i<=n;i++){string s;cin>>s;add(s);}intm;cin>>m;for(inti=1;i<=m;i++){string s;cin>>s;intt=exist(s);if(t!=0)add(s);if(t==0)cout<<"WRONG"<<endl;elseif(t==1)cout<<"OK"<<endl;elsecout<<"REPEAT"<<endl;}}signedmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);slove();}

模板2

判断在所有字符串中，是否存在一个字符串是另一个字符串的前缀。

实现这个功能，我们需要给结点维护两个信息，一个是p a s s \mathrm {pass}pass，一个是e n d \mathrm {end}end。

p a s s \mathrm {pass}pass统计的是，当前结点被经过多少次，e n d \mathrm {end}end统计的是，以当前结点为终点的字符串有多少个。

那么我们只需要判断，是否存在一个结点的e n d \mathrm {end}end大于0 \mathrm 00的情况下，p a s s \mathrm {pass}pass至少为2 \mathrm 22。

所以只需要按顺序添加字符串，然后判断这个字符串的末尾结点的p a s s \mathrm{pass}pass是否大于1 \mathrm{1}1。

#include<bits/stdc++.h>usingnamespacestd;//#pragma GCC optimize(2)#defineintlonglong#defineendl'\n'#definePIIpair<int,int>#defineINF1e18constintM=1e5;constintN=1e4;inttr[50*N+50][27];intEnd[50*N+50];intPass[50*N+50];intcnt=1;intexist(string&s){intnext=1;for(inti=0;i<s.size();i++){if(!tr[next][s[i]-'0']){return0;}next=tr[next][s[i]-'0'];}returnnext;}voidadd(string&s){intnext=1;Pass[next]++;for(inti=0;i<s.size();i++){if(!tr[next][s[i]-'0']){tr[next][s[i]-'0']=++cnt;}next=tr[next][s[i]-'0'];Pass[next]++;}End[next]++;return;}voidslove(){for(inti=1;i<=cnt;i++){for(intj=0;j<10;j++){tr[i][j]=0;}Pass[i]=0;End[i]=0;}cnt=1;intn;cin>>n;intflag=0;vector<string>v(n+1);for(inti=1;i<=n;i++){cin>>v[i];add(v[i]);}for(inti=1;i<=n;i++){intnext=exist(v[i]);if(Pass[next]>1){flag=1;}}if(flag)cout<<"NO"<<endl;elsecout<<"YES"<<endl;}signedmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);intT;cin>>T;while(T--)slove();}

异或字典树

将每个二进制当作一个字符串s t r i n g \mathrm {string}string，构建一棵字符集为{ 0 , 1 } \mathrm {\{0,1\}}{0,1}的异或字典树。

最长异或路径

给定一棵n \mathrm nn个点的带权树，结点下标从1 \mathrm 11开始到n \mathrm nn。求树中所有异或路径的最大值。

异或路径指的是树上两个结点之间唯一路径上的所有边权的异或值。

解

找到一条路径( X , Y ) \mathrm {(X,Y)}(X,Y)使得路径异或值最大，而路径( X , Y ) \mathrm {(X,Y)}(X,Y)的异或值这其实等价于X \mathrm {X}X到L C A ( X , Y ) \mathrm {LCA(X,Y)}LCA(X,Y)的路径异或值异或值异或上Y \mathrm {Y}Y到L C A ( X , Y ) \mathrm {LCA(X,Y)}LCA(X,Y)的路径异或值。

进一步地等价于X \mathrm {X}X到R o o t \mathrm {Root}Root的路径异或值异或上Y \mathrm YY到R o o t \mathrm {Root}Root的路径异或值。

所以，我们其实只需要预处理出每个点到R o o t \mathrm {Root}Root的路径异或值，特别注意R o o t \mathrm {Root}Root到R o o t \mathrm {Root}Root自己的路径异或值是0 00。

所以我们现在的问题就变成，任选这n \mathrm nn个值（n \mathrm nn个路径异或值）中的两个，使得二者的异或之和最大。

把这n \mathrm nn个异或值用二进制方式存入字典树内，不妨令所有异或值均具有32 \mathrm {32}32位，我们从最高位开始存入字典树，树高是32 \mathrm {32}32。

将所有二进制存入字典树后，我们要想最终异或的结果最大，那么就要尽可能地让高位二进制位不同。

枚举每个异或值作为答案之一，另外一个异或值就需要贪心地从t i r e \mathrm {tire}tire树里面找。

代码

#include<bits/stdc++.h>usingnamespacestd;//#pragma GCC optimize(2)#defineintlonglong#defineendl'\n'#definePIIpair<int,int>#defineINF1e18constintN=1e5+7;inttrie[32*N][3];intcnt=1;voidadd(string&s){intst=1;for(inti=0;i<s.size();i++){if(!trie[st][s[i]-'0']){trie[st][s[i]-'0']=++cnt;}st=trie[st][s[i]-'0'];}}// 查找与给定字符串 s 异或后最大的字符串intquery(string&s){intans=0,st=1,deep=31;for(inti=0;i<s.size();i++){intf=s[i]-'0';if(trie[st][1^f]){ans+=(1ll<<deep);st=trie[st][1^f];}else{st=trie[st][f];}deep--;}returnans;}voidslove(){intn;cin>>n;vector<PII>g[n+1];for(inti=1;i<=n-1;i++){intu,v,w;cin>>u>>v>>w;g[u].emplace_back(v,w);}vector<int>dp(n+1,0);function<void(int,int)>dfs=[&](intu,intfa){for(auto[v,w]:g[u]){if(v==fa)continue;dp[v]=dp[u]^w;dfs(v,u);}};dfs(1,0);intans=0;for(inti=1;i<=n;i++){string s;for(intj=31;j>=0;j--){if(dp[i]&(1ll<<j))s+='1';elses+='0';}add(s);}for(inti=1;i<=n;i++){string s;for(intj=31;j>=0;j--){if(dp[i]&(1ll<<j))s+='1';elses+='0';}ans=max(ans,query(s));}cout<<ans<<endl;}signedmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);slove();}