传送门
Solution
复习下tire(￣▽￣)／
裸的可持久化tire，我用树剖求了下LCA
Code
#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>#define F(i,a,b) for(register int i=(a);i<=(b);i++)#define E(i,u) for(register int i=head[u],v;i;i=E[i].nxt)using namespace std;inline int read() { ???int x=0,f=1;char c=getchar(); ???while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();} ???while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar(); ???return x*f;} const int N=1e5+10;int n,cnt,tot,q;int head[N],fa[N],top[N],dep[N],rt[N],siz[N],son[N];char ch[N][20];struct Edge{int to,nxt;char *ch;}E[N<<1];struct Node{int son[27],val;}nd[N<<4];inline void add(int u,int v,char *s) {E[++cnt]=(Edge){v,head[u],s};head[u]=cnt;}void ins(int o1,int &o2,int dep,char *s,int len) { ???nd[o2=++tot]=nd[o1];nd[o2].val++;if(dep>len) return ; ???ins(nd[o1].son[s[dep]-'a'],nd[o2].son[s[dep]-'a'],dep+1,s,len);}int qry(int o,char *s,int len) { ???F(i,1,len) o=nd[o].son[s[i]-'a']; ???return nd[o].val;}void dfs1(int u,int pre) { ???siz[u]=1;fa[u]=pre;dep[u]=dep[pre]+1; ???E(i,u) if((v=E[i].to)!=pre) { ???????ins(rt[u],rt[v],1,E[i].ch,strlen(E[i].ch+1)); ???????dfs1(v,u); siz[u]+=siz[v]; ???????if(siz[son[u]]<siz[v]) son[u]=v; ???}}void dfs2(int u,int pre) { ???if(son[pre]==u) top[u]=top[pre]; else top[u]=u; ???if(son[u]) dfs2(son[u],u); ???E(i,u) if((v=E[i].to)!=pre&&v!=son[u]) dfs2(v,u);}int LCA(int x,int y) { ???while(top[x]!=top[y]) { ???????if(dep[top[x]]<dep[top[y]]) swap(x,y); ???????x=fa[top[x]]; ???} ???return dep[x]<dep[y]?x:y;}int main() { ???n=read(); ???F(i,1,n-1) { ???????int a=read(),b=read();scanf("%s",ch[i]+1); ???????add(a,b,ch[i]);add(b,a,ch[i]); ???} ???dfs1(1,0);dfs2(1,0); ???q=read(); ???while(q--) { ???????int u=read(),v=read();scanf("%s",ch[0]+1); ???????int len=strlen(ch[0]+1); ???????int ans=qry(rt[u],ch[0],len)+qry(rt[v],ch[0],len) ???????????-2*qry(rt[LCA(u,v)],ch[0],len); ???????printf("%d\n",ans); ???} ???return 0;}[bzoj4477 Jsoi2015]字符串树 (可持久化trie)
原文地址：https://www.cnblogs.com/Menteur-Hxy/p/9737883.html