[jsoi2015] string tree

Be persistent trie

link ：[P6088 JSOI2015] String tree - Luogu | New ecology of computer science education (luogu.com.cn)

The question ： Given a tree , Edge weight is string , Ask the path many times u To v How many prefixes do all strings of all edges that pass have w.

Answer key ： Persistent dictionary tree maintenance , Every time $u,v$ Of $lca$, Then you can add the query in two sections .

//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>

using namespace std;
typedef pair<int,string> P;
const int maxn=1e5+5;

string w;
int n,m,u,v;
int dep[maxn],lg[maxn],fa[maxn][18];
int p[maxn*10][26],rt[maxn],ct[maxn*10],now;
vector<P>ed[maxn];

void insert(int u,int v,string s)
{
    
	rt[v]=++now; 
	int l=rt[u],r=rt[v]; ct[r]=ct[l]+1;
	for(int i=0;i<s.length();i++)
	{
    
		int q=s[i]-'a';
		for(int j=0;j<=25;j++)p[r][j]=p[l][j];
		p[r][q]=++now,l=p[l][q],r=p[r][q],ct[r]=ct[l]+1;
	}
	return;
}

int query(int u,int v,string s)
{
    
	int l=rt[u],r=rt[v];
	for(int i=0;i<s.length();i++)
	{
    
		l=p[l][s[i]-'a'],r=p[r][s[i]-'a'];
	}
	return ct[r]-ct[l];	
}

int LCA(int x,int y)
{
    
	if(dep[x]<dep[y])swap(x,y);
	while(dep[x]>dep[y])
	{
    
		x=fa[x][lg[dep[x]-dep[y]]-1];
	}
	if(x==y)return x;
	for(int i=17;i>=0;i--)
	{
    
		if(fa[x][i]!=fa[y][i])
		{
    
			x=fa[x][i],y=fa[y][i];
		}
	}
	return fa[x][0];
}

void dfs(int x,int f,string s)
{
    
	dep[x]=dep[f]+1,fa[x][0]=f;
	if(s.length())insert(f,x,s);
	for(int i=1;i<=17;i++)
	{
    
		fa[x][i]=fa[fa[x][i-1]][i-1];
	}
	for(auto y:ed[x])
	{
    
		if(y.first!=f)dfs(y.first,x,y.second);
	}
	return;
}

int Query(int x,int y,string s)
{
    
	int lca=LCA(x,y);
	return query(lca,x,s)+query(lca,y,s);
}

int main()
{
    
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)lg[i]=lg[i-1]+(!(i&i-1));
	for(int i=1;i<n;i++)
	{
    
		cin>>u>>v>>w;
		ed[u].push_back(P(v,w));
		ed[v].push_back(P(u,w)); 
	}
	dfs(1,0,""),cin>>m;
	for(int i=1;i<=m;i++)
	{
    
		cin>>u>>v>>w;
		cout<<Query(u,v,w)<<"\n";
	}
	return 0;
}