Chrysanthemum's Blog

这是一道裸的可持久化trie树。这个方法就不多说了，详见“初探主席树”及“cout on a tree”。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100010
using namespace std;
int n,u,v,cnt,l,q;
int edgenum,vet[2*N],next[2*N],head[2*N],root[N];
int f[N],d[N],num[N],son[N],top[N];
struct node{int sum,son[30];}tr[10*N];
char str[15],s[N][15];
void add(int u,int v)
{
	edgenum++;
	vet[edgenum]=v;
	next[edgenum]=head[u];
	head[u]=edgenum;
}
void dfs(int u,int fa,int dep)
{
	f[u]=fa;
	d[u]=dep;
	num[u]=1;
	int maxnum=0;
	for (int e=head[u];e;e=next[e])
	{
		int v=vet[e];
		if (v!=fa)
		{
			dfs(v,u,dep+1);
			num[u]+=num[v];
			if (num[v]>maxnum){maxnum=num[v];son[u]=v;}
		}
	}
}
void dfs(int u,int number)
{
	top[u]=number;
	if (!son[u]) return;
	dfs(son[u],number);
	for (int e=head[u];e;e=next[e])
	{
		int v=vet[e];
		if (v!=f[u]&&v!=son[u]) dfs(v,v);
	}
}
int getlca(int u,int v)
{
	while (top[u]!=top[v])
	{
		if (d[top[u]]<d[top[v]]) swap(u,v);
		u=f[top[u]];
	}
	if (d[u]<d[v]) return u;else return v;
}
void change(int &p,int k,int dep)
{
	tr[++cnt]=tr[p];p=cnt;tr[p].sum++;
	if (dep==strlen(s[k])) return;
	change(tr[p].son[s[k][dep]-'a'],k,dep+1);
}
int ask(int p,int dep)
{
	if (p==0&&dep) return 0;
	if (dep==l) return tr[p].sum;
	return ask(tr[p].son[str[dep]-'a'],dep+1);
}
void dfs1(int u,int e)
{
	if (u!=1){root[u]=root[f[u]];change(root[u],(e+1)>>1,0);}
	for (int e=head[u];e;e=next[e])
	{
		int v=vet[e];
		if (v!=f[u]) dfs1(v,e);
	}
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<n;i++)
	{
		scanf("%d%d%s",&u,&v,s[i]);
		add(u,v);add(v,u);
	}
	dfs(1,0,1);
	dfs(1,1);
	dfs1(1,0);
	scanf("%d",&q);
	while (q--)
	{
		scanf("%d%d%s",&u,&v,str);
		l=strlen(str);
		printf("%d\n",ask(root[u],0)+ask(root[v],0)-2*ask(root[getlca(u,v)],0));
	}
}

还有一种我在练习赛上自己yy的一种方法。然而，有些复杂（我是有自知之明的），文字解释起来非常复杂，代码放着，有兴趣的人可以自己研究一下。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100010
using namespace std;
typedef long long ll;
int n,q,cnt,l;
int edgenum,Edgenum,vet[2*N],next[2*N],head[2*N],Vet[10*N],Next[10*N],Head[10*N],x[N],y[N],a[N],b[N],lca[N];
ll dis[2*N],Ask[10*N],P[10*N],p[10*N],ans[N],mi[20],w[N],c[N],d[N];
int f[N],de[N],num[N],son[N],top[N],tr[10*N];
char s[20];
void add(int u,int v,ll w)
{
	edgenum++;
	vet[edgenum]=v;
	next[edgenum]=head[u];
	head[u]=edgenum;
	dis[edgenum]=w;
}
void dfs(int u,int fa,int dep)
{
	f[u]=fa;
	de[u]=dep;
	num[u]=1;
	int maxnum=0;
	for (int e=head[u];e;e=next[e])
	{
		int v=vet[e];
		if (v!=fa)
		{
			dfs(v,u,dep+1);
			num[u]+=num[v];
			if (num[v]>maxnum){maxnum=num[v];son[u]=v;}
		}
	}
}
void dfs(int u,int number)
{
	top[u]=number;
	if (!son[u]) return;
	dfs(son[u],number);
	for (int e=head[u];e;e=next[e])
	{
		int v=vet[e];
		if (v!=f[u]&&v!=son[u]) dfs(v,v);
	}
}
int getlca(int u,int v)
{
	while (top[u]!=top[v])
	{
		if (de[top[u]]<de[top[v]]) swap(u,v);
		u=f[top[u]];
	}
	if (de[u]<de[v]) return u;else return v;
}
void Add(int u,int v,ll w,ll opt)
{
	Edgenum++;
	Vet[Edgenum]=v;
	Next[Edgenum]=Head[u];
	Head[u]=Edgenum;
	Ask[Edgenum]=w;
	P[Edgenum]=opt;
}
int asksum(ll x)
{
	int ans=0;
	while (x)
	{
		ans+=tr[x];
		x-=((x)&(-x));
	}
	return ans;
}
void tradd(ll x,int val)
{
	while (x<=cnt)
	{
		tr[x]+=val;
		x+=((x)&(-x));
	}
}
void dfs(int u)
{
	for (int e=Head[u];e;e=Next[e])
	{
		int v=Vet[e];
		ans[v]+=(ll)asksum(Ask[e])*P[e];
	}
	for (int e=head[u];e;e=next[e])
	{
		int v=vet[e];
		if (v!=f[u])
		{
			tradd(dis[e],1);
			dfs(v);
			tradd(dis[e],-1);
		}
	}
}
int main()
{
	freopen("strings.in","r",stdin);
	freopen("strings.out","w",stdout);
	scanf("%d",&n);
	mi[0]=1;
	for (int i=1;i<=10;i++) mi[i]=mi[i-1]*31;
	for (int i=1;i<n;i++)
	{
		scanf("%d%d%s",&x[i],&y[i],s);
		l=strlen(s);
		w[i]=0;
		for (int j=0;j<l;j++)
			w[i]=w[i]*31+s[j]-'a'+1;
		w[i]=w[i]*mi[10-l];
		p[++cnt]=(ll)w[i];
		add(x[i],y[i],w[i]);add(y[i],x[i],w[i]);
	}
	dfs(1,0,1);
	dfs(1,1);
	scanf("%d",&q);
	for (int i=1;i<=q;i++)
	{
		scanf("%d%d%s",&a[i],&b[i],s);
		lca[i]=getlca(a[i],b[i]);
		c[i]=0;
		l=strlen(s);
		for (int j=0;j<l;j++)
			c[i]=c[i]*31+s[j]-'a'+1;
		c[i]=c[i]*mi[10-l];
		d[i]=c[i]+(mi[10-l]-1)/30*('z'-'a'+1);
		p[++cnt]=(ll)c[i]-1;
		p[++cnt]=(ll)d[i];
		Add(a[i],i,d[i],1);
		Add(b[i],i,d[i],1);
		Add(lca[i],i,d[i],-2);
		Add(a[i],i,c[i]-1,-1);
		Add(b[i],i,c[i]-1,-1);
		Add(lca[i],i,c[i]-1,2);
	}
	sort(p+1,p+cnt+1);
	cnt=unique(p+1,p+cnt+1)-p-1;
	for (int i=1;i<=edgenum;i++)
		dis[i]=lower_bound(p+1,p+cnt+1,dis[i])-p;
	for (int i=1;i<=Edgenum;i++)
		Ask[i]=lower_bound(p+1,p+cnt+1,Ask[i])-p;
	dfs(1);
	for (int i=1;i<=q;i++)
		printf("%lld\n",ans[i]);
}