又是被水题坑了。。。
一直想不出来看题解说要什么主席树，于是开始打离线算法
结果打到一半发现要强制在线。。No!!!
发现直接AC自动机似乎可做？树剖之后在AC自动机上跑的时候判断一下不就好了吗!连线段树都不要
让后快乐切掉，速度还可以（废话，人家N^2暴力都跑得飞快）
#pragma GCC opitmize("O3")#pragma G++ opitmize("O3")#include #include #include #include #define vs (*s-'a')#define N 100010using namespace std;struct AcAutomation{ int son[N*10][26],f[N*10],c[N*10],cnt; queue q; vector p[N*10]; inline void clear(){ cnt=1; } inline void insert(char* s,int pos){ int x=1,l=0; for(;*s;++s,++l) x=son[x][vs]?son[x][vs]:son[x][vs]=++cnt; c[x]=l; p[x].push_back(pos); } inline void build(){ p[1].push_back(N); sort(p[1].begin(),p[1].end()); for(int i=0;i<26;++i) if(!son[1][i]) son[1][i]=1; else q.push(son[1][i]),f[son[1][i]]=1; for(int x;!q.empty();q.pop()){ x=q.front(); p[x].push_back(N); sort(p[x].begin(),p[x].end()); for(int i=0;i<26;++i) if(!son[x][i]) son[x][i]=son[f[x]][i]; else q.push(son[x][i]),f[son[x][i]]=son[f[x]][i]; } } inline int query(char* s,int l,int r){ int ans=0; for(int x=1;*s;++s){ x=son[x][vs]; for(int j=x;j>1;j=f[j]) if(c[j]>ans && *lower_bound(p[j].begin(),p[j].end(),l)<=r) { ans=c[j]; break; } } return ans; }}AC;char s[N][12],c[N];struct edge{ int v,nt; } G[N<<1];int h[N],d[N],f[N],top[N],son[N],sz[N];int l[N],r[N],n,m,cnt=0,clk=0,T;inline void adj(int x,int y){ G[++cnt]=(edge){y,h[x]}; h[x]=cnt; G[++cnt]=(edge){x,h[y]}; h[y]=cnt;}void dfs(int x,int p){ d[x]=d[p]+1; f[x]=p; sz[x]=1; for(int v,i=h[x];i;i=G[i].nt) if(!d[v=G[i].v]){ dfs(v,x); sz[x]+=sz[v]; if(sz[son[x]] d[top[y]]) x^=y^=x^=y; ans=max(ans,AC.query(s,l[top[y]],l[y])); } if(d[x]>d[y]) x^=y^=x^=y; return max(ans,AC.query(s,l[x],l[y]));}int main(){ scanf("%d%d",&n,&T); AC.clear(); for(int i=1;i<=n;++i) scanf("%s",s[i]); for(int x,i=2;i<=n;++i) scanf("%d",&x),adj(x,i); dfs(1,0); dgs(1,1); for(int i=1;i<=n;++i) AC.insert(s[i],l[i]); scanf("%d",&m); AC.build(); for(int x,y,ans=0;m--;){ scanf("%d%d%s",&x,&y,c); x^=ans; y^=ans; ans=gLca(x,y,c); printf("%d\n",ans); ans*=T; }}