萌萌买了一颗字符串树的种子，春天种下去以后夏天就能长出一棵很大的字 符串树。字符串树很奇特，树枝上都密密麻麻写满了字符串，看上去很复杂的样 子。 【问题描述】 字符串树本质上还是一棵树，即N个节点N-1条边的连通无向无环图，节点 从1到N编号。与普通的树不同的是，树上的每条边都对应了一个字符串。萌萌 和JYY在树下玩的时候，萌萌决定考一考JYY。每次萌萌都写出一个字符串S和 两个节点U,V，需要JYY立即回答U和V之间的最短路径（即,之间边数最少的 路径。由于给定的是一棵树，这样的路径是唯一的）上有多少个字符串以为前 缀。 JYY虽然精通编程，但对字符串处理却不在行。所以他请你帮他解决萌萌的难题。
输入第一行包含一个整数N，代表字符串树的节点数量。 接下来N-1行，每行先是两个数U,V，然后是一个字符串S,表示节点和U节 点V之间有一条直接相连的边，这条边上的字符串是S。输入数据保证给出的是一 棵合法的树。 接下来一行包含一个整数Q，表示萌萌的问题数。 接来下Q行，每行先是两个数U,V，然后是一个字符串S,表示萌萌的一个问 题是节点U和节点V之间的最短路径上有多少字符串以S为前缀。 输入中所有字符串只包含a-z的小写字母。 1<=N,Q<=100,000，且输入所有字符串长度不超过10。
输出Q行，每行对应萌萌的一个问题的答案。
By 佚名上传
[ Submit][ Status][ Discuss]-----------------------------
树链剖分+可持久化trie
每一条链开一个trie每个节点记录有几个字符串的前缀经过这里
最后把 u-v之间的每一条链统计一下
最后一条链不是完整的，前缀和减一下就好了
代码:
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #define For(i,x,y) for(int i=x;i<=y;++i) 5 using namespace std; 6 const int N = 1e5 + 5; 7 int n;int sz[N],son[N],top[N],fa[N],id[N],deep[N],_; 8 char q[N][11]; 9 int head[N],nxt[N*2],to[N*2];char s[N*2][11];int cnt; 10 void dfs1(int u,int fat){ 11 sz[u]=1; 12 for(int i=head[u];i;i=nxt[i]){ 13 int v=to[i];if(v!=fat){ 14 fa[v]=u;deep[v]=deep[u]+1; 15 For(j,0,strlen(s[i])-1) q[v][j]=s[i][j]; 16 dfs1(v,u);sz[u]+=sz[v]; 17 if(sz[v]>sz[son[u]]) son[u]=v; 18 } 19 } 20 } 21 int rt[N]; 22 //char k[10]; 23 struct Trie{ 24 int tot;int nxt[N*40][26];int sg[N*60]; 25 void ins(int nx,int p,char*s){ 26 int len=strlen(s); 27 if(!rt[p]) rt[p]=++tot;int node=rt[p]; 28 int node1=rt[nx]; 29 For(i,0,len-1){ 30 For(j,0,25) nxt[node][j]=nxt[node1][j]; 31 nxt[node][s[i]-'a']=++tot; 32 sg[tot]=sg[nxt[node1][s[i]-'a']]+1; 33 node=nxt[node][s[i]-'a']; 34 node1=nxt[node1][s[i]-'a']; 35 } 36 } 37 int pre(int p,char*s){ 38 int len=strlen(s); 39 int node=rt[p]; 40 For(i,0,len-1){node=nxt[node][s[i]-'a'];} 41 return sg[node]; 42 } 43 }T; 44 void dfs2(int u,int fat,int tp){ 45 id[u]=++_;top[u]=tp; 46 if(u!=1){ 47 if(tp==u) T.ins(0,id[u],q[u]); 48 else T.ins(id[u]-1,id[u],q[u]); 49 } 50 if(son[u]) dfs2(son[u],u,tp); 51 for(int i=head[u];i;i=nxt[i]){ 52 int v=to[i];if(v!=fat&&v!=son[u]){ 53 dfs2(v,u,v); 54 } 55 } 56 } 57 void add(int u,int v,char*t){ 58 nxt[++cnt]=head[u];head[u]=cnt;to[cnt]=v;For(i,0,strlen(t)-1) s[cnt][i]=t[i]; 59 nxt[++cnt]=head[v];head[v]=cnt;to[cnt]=u;For(i,0,strlen(t)-1) s[cnt][i]=t[i]; 60 } 61 char Q[11]; 62 int query(int u,int v){ 63 int res=0; 64 while(top[u]!=top[v]){ 65 if(deep[top[u]]<deep[top[v]]) swap(u,v); 66 res+=T.pre(id[u],Q); 67 u=fa[top[u]]; 68 } 69 if(deep[u]<deep[v]) swap(u,v); 70 // if(top[v]==v)res+=T.pre(id[u],Q); 71 res+=T.pre(id[u],Q)-T.pre(id[v],Q); 72 return res; 73 } 74 char tmp[10]; 75 int main(){ 76 // freopen("1.in","r",stdin); 77 // freopen("1.out","w",stdout); 78 scanf("%d",&n); 79 For(i,1,n-1){ 80 int u,v; 81 scanf("%d%d%s",&u,&v,tmp); 82 add(u,v,tmp); 83 } 84 dfs1(1,1);dfs2(1,1,1); 85 int m;scanf("%d",&m); 86 while(m--){ 87 int u,v; 88 scanf("%d%d%s",&u,&v,Q); 89 printf("%d\n",query(u,v)); 90 } 91 }
转载于:https://www.cnblogs.com/rwy233/p/6411392.html
