Description

Input

Output

Sample Input

4
1 2 ab
2 4 ac
1 3 bc
3
1 4 a
3 4 b
3 2 ab

Sample Output

2
1
1

Data Constraint

Soluiton

• 這題是典型的可持久化 Trie 樹！

• 由于每一個讀入的串長度不超過 10，所以 Trie 的深度也不會超過 10 。

• 例如有一條邊是 (u,v,s)，

• 那么我們將 v 從 u 上繼承信息，然后對于 v 的 Trie 樹，插入 s 這個串，將路徑上每一個點的權值都+1；

• 然后對于每一個詢問 (x,y,s)，用s在 x , y , lca(x,y) 中走他們各自的 Trie 樹，走到點 p，

• 那么 p 的權值就是這棵 Trie 樹有多少個串前綴有 s，

• 然后用 x 與 y 的值和 減去 兩倍的 lca(x,y) 的值。

Code

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N=100001; struct trie {int son[26],v; }tr[N*10]; int n,q,u,v,ans,tot; int first[N],next[N*2],en[N*2],len[N*2]; int dep[N],fa[N],f[N][20]; int que[N],g[N]; char w[N*2][12],s[12]; void insert(int x,int y) {next[++tot]=first[x];first[x]=tot;en[tot]=y;len[tot]=strlen(s+1);for(int i=1;i<=len[tot];i++) w[tot][i]=s[i]; } void add(int p,int now,int num) {for(int i=1;i<=len[num];i++){tr[now]=tr[p];tr[now].v++;p=tr[p].son[w[num][i]-'a'];tr[now].son[w[num][i]-'a']=++tot;now=tot;}tr[now].v++; } void bfs() {int l=0,r=que[1]=1;while(l<r){int x=que[++l];dep[x]=dep[f[x][0]=fa[x]]+1;for(int i=1;f[f[x][i-1]][i-1];i++) f[x][i]=f[f[x][i-1]][i-1];for(int i=first[x];i;i=next[i])if(en[i]!=fa[x]){fa[que[++r]=en[i]]=x;g[en[i]]=++tot;add(g[x],tot,i);}} } int lca(int x,int y) {if(dep[x]<dep[y]) swap(x,y);for(int i=log2(dep[x]);i>=0;i--)if(dep[f[x][i]]>=dep[y]) x=f[x][i];for(int i=log2(dep[x]);i>=0;i--)if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];return (x==y)?x:f[x][0]; } int find(int now,char *s) {int l=strlen(s+1);for(int i=1;i<=l;i++) now=tr[now].son[s[i]-'a'];return tr[now].v; } int main() {scanf("%d",&n);for(int i=1;i<n;i++){scanf("%d%d %s",&u,&v,s+1);insert(u,v);insert(v,u);}tot=0;bfs();scanf("%d",&q);while(q--){scanf("%d%d %s",&u,&v,s+1);ans=find(g[u],s)+find(g[v],s);ans-=find(g[lca(u,v)],s)*2;printf("%d\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 4061. 【JSOI2015】字符串树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。