正題

題面鏈接:https://www.luogu.com.cn/problem/P6088

---

題目大意

$n$個(gè)點(diǎn)的一棵樹，每條邊上有一個(gè)字符串，求一條路徑上有多少以詢問字符串為前綴的字符串。

---

解題思路

建立一個(gè)可持久化$Trie$，然后每個(gè)點(diǎn)繼承父親插入字符串。

然后詢問答案就是$$su{m}_x+su{m}_y?su{m}_{LCA(x,y)}$$

時(shí)間復(fù)雜度$O(n\log n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e5+10,T=17; struct node{int to,next,w; }a[N*2]; int n,m,cnt,tot,rt[N],dep[N],ls[N]; int f[N][T+1],ch[N*11][26],w[N*11]; char s[N][11],qr[11]; void addl(int x,int y,int w){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;return; } int Insert(int x,int k,int id,int lim){int y=++cnt;w[y]=w[x]+1;if(k>=lim)return y;memcpy(ch[y],ch[x],sizeof(ch[y]));int c=s[id][k]-'a';ch[y][c]=Insert(ch[x][c],k+1,id,lim);return y; } int Ask(int x,int lim){for(int i=0;i<lim;i++)x=ch[x][qr[i]-'a'];return w[x]; } void dfs(int x,int fa){dep[x]=dep[fa]+1;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa)continue;rt[y]=Insert(rt[x],0,a[i].w,strlen(s[a[i].w]));f[y][0]=x;dfs(y,x);}return; } int LCA(int x,int y){if(dep[x]>dep[y])swap(x,y);for(int i=T;i>=0;i--)if(dep[f[y][i]]>=dep[x])y=f[y][i];if(x==y)return x;for(int i=T;i>=0;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];return f[x][0]; } int main() {scanf("%d",&n);for(int i=1;i<n;i++){int x,y;scanf("%d%d%s",&x,&y,s[i]);addl(x,y,i);addl(y,x,i);}dfs(1,1);for(int j=1;j<=T;j++)for(int i=1;i<=n;i++)f[i][j]=f[f[i][j-1]][j-1];scanf("%d",&m);while(m--){int x,y,lim;scanf("%d%d",&x,&y);scanf("%s",qr);lim=strlen(qr);printf("%d\n",Ask(rt[x],lim)+Ask(rt[y],lim)-2*Ask(rt[LCA(x,y)],lim));}return 0; }

總結(jié)

以上是生活随笔為你收集整理的P6088-[JSOI2015]字符串树【可持久化Trie,LCA】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。