题解 P6088 【[JSOI2015]字符串树】

· · 题解

提供第二种解法：简单 \text{stl}，\text{hash}，树剖。

前言

题目大意

给一棵无根树，边有字符串权值，多次询问，每次询问给出字符串 s，求树上两点间路径中以 s 为前缀的边数。

--- #### 做题思考 看题，题面看完没什么想法，第一眼只想到了 $O(n \times len)$ 预处理 $\text{hash}$ 值，$O(nq)$ 暴力查询。 前缀匹配问题，看看能不能上 $\text{AC}$ 自动机之类的东西？好像不太行。 第一时间没有想到 $\text{trie}$ ，思路断掉。 看眼数据范围有没有特殊之处。“输入所有字符串长度不超过 $10$ 且只包含 `a~z` 的小写字母。” 长度不超过 $10$ ？那我的预处理就能接受了啊！能不能优化一下查询？ 树上两点，询问是求数量，有可加性，那可以上树剖啊！ 但是线段树怎么写？把所有字符串都记一遍？不现实。 那就换个数据结构！但是用什么呢？ 这时候是拼底蕴的时候了。如果你做过[这道题](https://www.luogu.com.cn/problem/P5838)并仔细看了题解，你应该发现在第一页最下面有[Fzzzz](https://www.luogu.com.cn/user/174045)的另类做法。 $\text{vector}$ 存每个品种在树剖序（就是 $\text{dfs}$ 序） 中出现的位置，查询就在跳 $\text{top}$ 时二分查找 顶部和底部的 $\text{dfs}$ 序在询问品种的 $\text{vector}$ 中的位置差。他的做法在那道题中表现优秀，非常便于编写和调试。 回到这题，我们也可以借用这种方法。先把边权转为点权，然后将树剖的线段树换成 $\text{vector}$，把询问字符串的 $\text{hash}$ 值离散化后作为 $\text{vector}$ 的下标，每次查询在 $\text{vector}$ 上二分。 时间复杂度 $O(n \log n \times len\ +\ q \log n)$。 不要忘了把每个点的 $\text{dfs}$ 序加入 $\text{vector}$ 后要排序。 注意 $\text{vector}$ 的大小。 注意二分的写法。 记得最后把 $\text{lca}$ 的贡献减掉。 --- #### 代码 代码里使用了 $\text{map}$ 离散化，常数略大，不开 $\text{O2}$ 最大点需要 $1.9s$，开了需要 $650ms$。~~但是时限 $2s$，没想到吧~~ 代码较长，原因是树剖和 $\text{hash}$ 预处理长度较大。 相信听懂了就不需要注释。 不加反作弊~~谁抄这个诡异的做法啊~~。 ``` #include<algorithm> #include<cstring> #include<cstdio> #include<vector> #include<map> typedef unsigned long long ull; const int maxn=1e5+5; const int maxm=maxn*2+5; const int maxl=1e1+5; const int jz=131; struct edge{ int to; int next; char str[maxl]; void out(){ for(int i=1;i<=(int)strlen(str+1);i++)printf("%c",str[i]); puts(""); return; } }qxx[maxm]; int qxx_cnt,h[maxn]; void add(int x,int y,char *s){ int len=strlen(s+1); qxx_cnt++; for(int i=1;i<=len;i++)qxx[qxx_cnt].str[i]=s[i]; qxx[qxx_cnt].to=y; qxx[qxx_cnt].next=h[x]; h[x]=qxx_cnt; return; } void ad(int x,int y,char *s){ add(x,y,s); add(y,x,s); return; } ull hash[maxn][maxl]; char up[maxn][maxl]; int d[maxn],size[maxn],fa[maxn],son[maxn]; void init(int x,int f){ d[x]=d[f]+1; size[x]=1; fa[x]=f; for(int i=h[x];i;i=qxx[i].next){ int v=qxx[i].to; if(v==f)continue; int len=strlen(qxx[i].str+1); hash[v][0]=1; for(int j=1;j<=len;j++)up[v][j]=qxx[i].str[j]; for(int j=1;j<=len;j++)hash[v][j]=hash[v][j-1]*jz+(int)qxx[i].str[j]; init(v,x); size[x]+=size[v]; if(size[v]>size[son[x]])son[x]=v; } return; } int dfn[maxn],top[maxn]; int alt; void topen(int x,int tp){ top[x]=tp; dfn[x]=++alt; if(son[x])topen(son[x],tp); for(int i=h[x];i;i=qxx[i].next){ int v=qxx[i].to; if(v==fa[x]||v==son[x])continue; topen(v,v); } return; } std::vector<int>apr[maxn*maxl]; std::map<ull,int>mp; int mcnt; int n,q; int get(int l,int r,ull nhash){ int id=mp[nhash]; int rig=std::upper_bound(apr[id].begin(),apr[id].end(),r)-apr[id].begin(), lef=std::lower_bound(apr[id].begin(),apr[id].end(),l)-apr[id].begin(); return rig-lef; } int tian(int x,int y,char *str){ ull nhash=1; int len=strlen(str+1); for(int i=1;i<=len;i++)nhash=nhash*jz+(int)str[i]; if(!mp[nhash])return 0; int ans=0; while(top[x]!=top[y]){ if(d[top[x]]<d[top[y]])std::swap(x,y); ans+=get(dfn[top[x]],dfn[x],nhash); x=fa[top[x]]; } if(d[x]<d[y])std::swap(x,y); ans+=get(dfn[y],dfn[x],nhash); ans-=(hash[y][len]==nhash); return ans; } signed main(){ scanf("%d",&n); for(int i=1;i<=n-1;i++){ int x,y; char str[maxl]; scanf("%d%d %s",&x,&y,str+1); ad(x,y,str); } init(1,1); topen(1,1); for(int i=2;i<=n;i++){ int len=(int)strlen(up[i]+1); for(int j=1;j<=len;j++){ if(!mp[hash[i][j]])mp[hash[i][j]]=++mcnt; apr[mp[hash[i][j]]].push_back(dfn[i]); } } for(int i=1;i<=mcnt;i++)std::sort(apr[i].begin(),apr[i].end()); scanf("%d",&q); for(int i=1;i<=q;i++){ int x,y; char str[maxl]; scanf("%d%d %s",&x,&y,str+1); printf("%d\n",tian(x,y,str)); } return 0; } ``` --- #### 为什么会想到这个做法 因为上来想到了 $\text{hash}$ ，一看长度很小发现可行，问题直接转化为询问一个数在树上两点间路径中的出现次数，这就是上面那题。 推荐把上题也做了。 感谢你的阅读，再见！