[Jsoi2015]字符串树

树链剖分 可持久化Tire树 Tire

题面

字符串树本质上还是一棵树，即$N$个节点$N-1$条边的连通无向无环图，节点
从$1$到$N$编号。与普通的树不同的是，树上的每条边都对应了一个字符串。萌萌
和$JYY$在树下玩的时候，萌萌决定考一考$JYY$。每次萌萌都写出一个字符串$S$和
两个节点$U,V$，需要$JYY$立即回答$U$和$V$之间的最短路径（即之间边数最少的
路径。由于给定的是一棵树，这样的路径是唯一的）上有多少个字符串以为前
缀。

• $n,Q\leq10^5$

解析

维护树上距离，我能想到的也只有树链剖分了。
树链剖分维护树上距离，实际上是通过每个点到根节点的距离来进行的。

那么这题也一样。
维护一下每个点到根节点的字符串。
又因为求的是前缀，可以用$Tire$树维护。
注意到各节点字符串是有重复的。为了节省空间，可以把$Tire$树可持久化。
然后就完事了。

其实我一开始做这题时不知道怎么把字符串作为边权。。。

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
#define re register
#define il inline
#define ls x<<1
#define rs x<<1|1
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=1e5+100;
int n,q,h[N],cnt,sz[N],son[N],f[N],top[N],d[N],rt[N*100],tot;
struct Tire{int son[26],w;}t[N*60];
struct Edge{int to,nxt;char *s;}e[N<<1];
il void add(re int u,re int v,re char *s){e[++cnt]=(Edge){v,h[u],s};h[u]=cnt;}
char op[N][15];
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void Insert(re int &u,re char *s,re int x,re int n)
{
  t[++tot]=t[u];u=tot;++t[u].w;
  if(x>n) return;
  Insert(t[u].son[s[x]-'a'],s,x+1,n);
}
il ll Query(re int u,re char *s,re int n)
{
  fp(i,1,n) u=t[u].son[s[i]-'a'];
  return t[u].w;
}
il void dfs1(re int u,re int fa)
{
  f[u]=fa;sz[u]=1;d[u]=d[fa]+1;
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v==fa) continue;
      Insert(rt[v]=rt[u],e[i].s,1,strlen(e[i].s+1));
      dfs1(v,u);
      sz[u]+=sz[v];
      if(sz[v]>sz[son[u]]) son[u]=v;
    }
}
il void dfs2(re int u,re int up)
{
  top[u]=up;
  if(son[u]) dfs2(son[u],up);
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v==f[u]||v==son[u]) continue;
      dfs2(v,v);
    }
}
il int getLCA(re int u,re int v)
{
  while(top[u]^top[v])
    {
      if(d[top[u]]<d[top[v]]) swap(u,v);
      u=f[top[u]];
    }
  return d[u]<d[v]?u:v;
}
int main()
{
  memset(h,-1,sizeof(h));
  n=gi();
  fp(i,1,n-1)
    {
      re int u=gi(),v=gi();scanf("%s",op[i]+1);
      add(u,v,op[i]);add(v,u,op[i]);
    }
  dfs1(1,0);dfs2(1,1);
  q=gi();
  while(q--)
    {
      re int u=gi(),v=gi(),lca=getLCA(u,v);scanf("%s",op[0]+1);
      re int len=strlen(op[0]+1);
      printf("%lld\n",Query(rt[u],op[0],len)+Query(rt[v],op[0],len)-2*Query(rt[lca],op[0],len));
    }
  return 0;
}