自动搬运

查看原文

来自洛谷，原作者为

	serene_analysis 我所有的欲望和沉思，都是这个世界缓缓呼出的气流

搬运于2025-08-24 22:17:17，当前版本为作者最后更新于2021-06-19 10:56:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

前言

• 和我上一篇题解不太一样，这篇题解更偏向于讲做法，会顺带提及想到这种做法的心路历程。原因最后说。

题目大意

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

$n,q \le 10^5$， 所有字符串长度不超过 $10$，只含小写字母。

做题思考

看题，题面看完没什么想法，第一眼只想到了 $O(n \times len)$ 预处理 $\text{hash}$ 值，$O(nq)$ 暴力查询。

前缀匹配问题，看看能不能上 $\text{AC}$ 自动机之类的东西？好像不太行。

第一时间没有想到 $\text{trie}$ ，思路断掉。

看眼数据范围有没有特殊之处。“输入所有字符串长度不超过 $10$ 且只包含 a~z 的小写字母。”

长度不超过 $10$ ？那我的预处理就能接受了啊！能不能优化一下查询？

树上两点，询问是求数量，有可加性，那可以上树剖啊！

但是线段树怎么写？把所有字符串都记一遍？不现实。

那就换个数据结构！但是用什么呢？

这时候是拼底蕴的时候了。如果你做过这道题并仔细看了题解，你应该发现在第一页最下面有Fzzzz的另类做法。 $\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}$ ，一看长度很小发现可行，问题直接转化为询问一个数在树上两点间路径中的出现次数，这就是上面那题。

推荐把上题也做了。

感谢你的阅读，再见！