自动搬运

查看原文

来自洛谷，原作者为

	mrsrz 故障机器人

搬运于2025-08-24 22:05:33，当前版本为作者最后更新于2019-06-05 13:00:55，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

一道比较简单的数据结构题。

如果只有一种字符串，那么我们可以直接树链剖分+线段树来解决。

这里有多种字符串，那么我们还是树链剖分，然后对每种不同的字符串开线段树就可以了。空间用动态开点来解决。

操作2、3就是基本的线段树区间修改区间查询。操作1直接询问LCA即可。

对于判断字符串相等的问题，由于字符串长度不超过6，因此我们把字符串看做一个27进制数，用long long存，map离散化即可。

设字符串总数为$S$，则时间复杂度$O(n+m\log^2 n+S\log n)$，空间复杂度$O(n+S\log n)$。

Code：

#include<iostream>
#include<vector>
#include<cstring>
#include<map>
using namespace std;
typedef long long LL;
const int N=1e5+5,M=N*5;
char ss[233];
vector<int>G[N];
int n,m,fa[N],son[N],top[N],sz[N],dfn[N],idx,dep[N],rt[M],ls[M*20],rs[M*20],d[M*20],tot,num;
map<LL,int>ys;
inline LL Hx(char*s,int n){
	LL ret=0,x=1;
	for(int i=2;i<n;++i,x*=27)
	ret+=(s[i]-'a'+1)*x;
	return ret;
}
void dfs(int now){
	sz[now]=1;
	for(int to:G[now])
	if(!dep[to]){
		dep[to]=dep[now]+1,fa[to]=now,dfs(to);
		sz[now]+=sz[to];
		if(!son[now]||sz[son[now]]<sz[to])son[now]=to;
	}
}
void dfs2(int now){
	dfn[now]=++idx;
	if(son[now])top[son[now]]=top[now],dfs2(son[now]);
	for(int to:G[now])
	if(to!=son[now]&&to!=fa[now])dfs2(top[to]=to);
}
inline int LCA(int x,int y){
	while(top[x]!=top[y])
	if(dep[top[x]]>dep[top[y]])x=fa[top[x]];else y=fa[top[y]];
	return dep[x]<dep[y]?x:y;
}
inline int dist(int u,int v){return dep[u]+dep[v]-2*dep[LCA(u,v)];}
void add(int&o,int l,int r,const int&pos){
	if(!o)o=++tot;
	++d[o];
	if(l<r){
		const int mid=l+r>>1;
		if(pos<=mid)add(ls[o],l,mid,pos);else add(rs[o],mid+1,r,pos);
	}
}
int erase(int&o,int l,int r,const int&L,const int&R){
	if(!o)return 0;
	int ret=0;
	if(L<=l&&r<=R){
		ret+=d[o],o=0;return ret;
	}
	const int mid=l+r>>1;
	if(L<=mid)ret+=erase(ls[o],l,mid,L,R);
	if(mid<R)ret+=erase(rs[o],mid+1,r,L,R);
	d[o]=d[ls[o]]+d[rs[o]];
	if(!d[o])o=0;
	return ret;
}
int erase(int&o,int x,int y){
	int ret=0;
	while(top[x]!=top[y])
	if(dep[top[x]]>dep[top[y]])
	ret+=erase(o,1,n,dfn[top[x]],dfn[x]),x=fa[top[x]];else
	ret+=erase(o,1,n,dfn[top[y]],dfn[y]),y=fa[top[y]];
	if(dep[x]<dep[y])ret+=erase(o,1,n,dfn[x],dfn[y]);else ret+=erase(o,1,n,dfn[y],dfn[x]);
	return ret;
}
int query(int o,int l,int r,const int&L,const int&R){
	if(!o)return 0;
	if(L<=l&&r<=R)return d[o];
	const int mid=l+r>>1;
	if(L<=mid&&mid<R)return query(ls[o],l,mid,L,R)+query(rs[o],mid+1,r,L,R);
	if(L<=mid)return query(ls[o],l,mid,L,R);return query(rs[o],mid+1,r,L,R);
}
int query(int o,int x,int y){
	int ret=0;
	while(top[x]!=top[y])
	if(dep[top[x]]>dep[top[y]])
	ret+=query(o,1,n,dfn[top[x]],dfn[x]),x=fa[top[x]];else
	ret+=query(o,1,n,dfn[top[y]],dfn[y]),y=fa[top[y]];
	if(dep[x]<dep[y])ret+=query(o,1,n,dfn[x],dfn[y]);else ret+=query(o,1,n,dfn[y],dfn[x]);
	return ret;
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<n;++i){
		int u,v;
		cin>>u>>v;
		G[u].push_back(v),G[v].push_back(u);
	}
	dfs(dep[1]=1),dfs2(1);
	ss[0]=ss[1]=' ';
	for(int i=1,k;i<=n;++i)
	for(cin>>k;k--;){
		cin>>(ss+2);
		LL hx=Hx(ss,strlen(ss));
		if(!ys.count(hx))ys[hx]=++num;
		add(rt[ys[hx]],1,n,dfn[i]);
	}
	while(m--){
		cin>>ss;
		if(*ss=='q'){
			cin>>ss;
			if(ss[1]=='p'){
				int u,v;
				cin>>u>>v;
				cout<<dist(u,v)<<'\n';
			}else{
				int u,v;
				cin>>u>>v>>ss;
				LL hx=Hx(ss,strlen(ss));
				if(!ys.count(hx))cout<<"0\n";else
				cout<<query(rt[ys[hx]],u,v)<<'\n';
			}
		}else{
			int u,v;
			cin>>ss>>u>>v>>ss;
			LL hx=Hx(ss,strlen(ss));
			if(!ys.count(hx))cout<<"0\n";else
			cout<<erase(rt[ys[hx]],u,v)<<'\n';
		}
	}
	return 0;
}