【JSOI2015】字符串树

题面

http://darkbzoj.tk/problem/4477

题解

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<map>
#define ri register int
#define N 200500
using namespace std;

int n,fa[N][20],tot=0,dep[N];
vector<int> to[N],s[N];
char st[N][15];
int root[N],sum[N*10];
int ch[N*10][26];
char stt[15];

void insert(int &x,int y,int ss) {
  if (!x) x=++tot;
  int now=x;
  sum[now]=sum[y]+1; for (ri i=0;i<26;i++) ch[now][i]=ch[y][i];
  for (ri i=1,l=strlen(st[ss]+1);i<=l;i++) {
    int c=st[ss][i]-'a';
    ch[now][c]=++tot;
    now=ch[now][c]; y=ch[y][c];
    sum[now]=sum[y]+1; if (y) for (ri i=0;i<26;i++) ch[now][i]=ch[y][i];
  }
}

void maketree(int x,int ff,int ss,int d) {
  dep[x]=d;
  insert(root[x],root[ff],ss);
  fa[x][0]=ff;
  for (ri i=1;i<=18;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
  for (ri i=0;i<to[x].size();i++) if (to[x][i]!=ff) maketree(to[x][i],x,s[x][i],d+1);
}

int lca(int x,int y){
  if (dep[x]<dep[y]) swap(x,y);
  for (ri i=18;i>=0;i--) if (dep[fa[x][i]]>=dep[y]) x=fa[x][i];
  if (x==y) return x;
  for (ri i=18;i>=0;i--) if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
  return fa[x][0];
}

int cha(int x) {
  int now=root[x];
  for (ri i=1,l=strlen(stt+1);i<=l;i++) {
    int c=stt[i]-'a';
    now=ch[now][c];
  }
  return sum[now];
}

int main() {
  int a,b,u,v;
  scanf("%d",&n);
  tot=0;
  for (ri i=1;i<n;i++) {
    scanf("%d %d %s",&a,&b,st[i]+1);
    to[a].push_back(b); s[a].push_back(i);// s[a].push_back(st);
    to[b].push_back(a); s[b].push_back(i);// s[b].push_back(st);
  }
  maketree(1,1,0,1);
  int q;
  scanf("%d",&q);
  for (ri i=1;i<=q;i++) {
    scanf("%d %d %s",&u,&v,stt+1);
    printf("%d
",cha(u)+cha(v)-2*cha(lca(u,v)));
  }
  return 0;
}