Description
n个点形成一棵树，每个点有一个由‘A’、‘G’、‘C’、‘T’、‘U’组成的字符串s_i，同时有一个权值\(a_i\)。现在要支持在线单点修改\(a_i\)，或给出询问串\(S\)，查询一条路径上的点\(a_i\cdot b_i\)的和，\(b_i\)为\(s_i\)在\(S\)中出现次数。
Solution
考虑链怎么做：我们可以维护一个线段树分治结构，对于一个分治区间，维护这里所有点的AC自动机，记\(f_i\)为\(i\)节点在fail树上到根节点的\(a_i\)的和，这可以用树状数组维护。
转到树上，我们发现这里权值是累加的，我们可以用括号序，左括号加上权值，右括号再减去，这样树上一条路径就是维护两段区间和。Code
#include#include #include #include #include #define fo(i,j,k) for(int i=j;i<=k;++i)#define fd(i,j,k) for(int i=j;i>=k;--i)using namespace std;const int N=4e5+10,M=4e5+10,Z=19;flagint L[N],ln[N],a[N],tot=0,m=0;int S[M];struct edge{ int to[M],nx[M],ls[M*20],num; void link(int u,int v){ to[++num]=v,nx[num]=ls[u],ls[u]=num; }}T,F;int ch(char c) { return (c>'A')+(c>'C')+(c>'G')+(c>'T');}int dep[N],fa[N][Z+5],n;int tr[M*20][5],fail[M*20];int ct[M*20];int pl[N],pr[N],z[N<<1],rt[N<<2],sz[N<<2];int pos[N<<1][Z+5];char s[M];void pre(int x,int fr){ fa[x][0]=fr,dep[x]=dep[fr]+1; fo(i,1,Z) fa[x][i]=fa[fa[x][i-1]][i-1]; z[pl[x]=++m]=x; for(int i=T.ls[x];i;i=T.nx[i]){ int v=T.to[i]; if(v==fr) continue; pre(v,x); } z[pr[x]=++m]=-x;}queue d;int tt=0;int le[M*20],ri[M*20];void bl(int x){ le[x]=++tt; for(int i=F.ls[x];i;i=F.nx[i]) bl(F.to[i]); ri[x]=tt;}int gg=0;void build(int v=1,int l=1,int r=m,int dp=1){ rt[v]=++tot; fo(i,l,r){ int p=rt[v],x=z[i],t=x<0?-x:x; fo(j,L[t],L[t]+ln[t]-1){ int c=S[j]; if(!tr[p][c]) tr[p][c]=++tot; p=tr[p][c]; } pos[x+n][dp]=p; } d.push(rt[v]); while(!d.empty()){ int x=d.front();d.pop(); fo(i,0,4){ int o=tr[x][i]; if(!o) continue; int p=fail[x]; while(p && !tr[p][i]) p=fail[p]; fail[o]=tr[p][i]?tr[p][i]:rt[v]; d.push(o); } } fo(i,rt[v]+1,tot) F.link(fail[i],i); tt=0,bl(rt[v]),sz[v]=tt+1,tot++; fo(i,rt[v]+1,tot) F.ls[fail[i]]=0;F.num=0; if(l==r) return; int mid=(l+r)>>1; build(v<<1,l,mid,dp+1),build(v<<1|1,mid+1,r,dp+1);}void ad(int x,int t,int v){ for(;x<=sz[v];x+=x&-x) ct[x+rt[v]-1]+=t; }int sum(int x,int v){ int tmp=0; for(;x;x-=x&-x) tmp+=ct[x+rt[v]-1]; return tmp;}int qu(int v){ int l=strlen(s+1),p=rt[v],tmp=0; fo(i,1,l){ int c=ch(s[i]); while(p && !tr[p][c]) p=fail[p]; p=tr[p][c]?tr[p][c]:rt[v]; tmp+=sum(le[p],v); } return tmp;}void add(int x,int t,int v=1,int l=1,int r=m,int dp=1){ int p=pos[z[x]+n][dp]; ad(le[p],t,v),ad(ri[p]+1,-t,v); if(l==r) return; int mid=(l+r)>>1; x<=mid?add(x,t,v<<1,l,mid,dp+1):add(x,t,v<<1|1,mid+1,r,dp+1);}int qsum(int x,int y,int v=1,int l=1,int r=m){ if(l==x && r==y) return qu(v); int mid=(l+r)>>1; if(y<=mid) return qsum(x,y,v<<1,l,mid); else if(x>mid) return qsum(x,y,v<<1|1,mid+1,r); else return qsum(x,mid,v<<1,l,mid)+qsum(mid+1,y,v<<1|1,mid+1,r);}int ed;int lca(int u,int v){ fd(i,Z,0) if(dep[fa[u][i]]>=dep[v]) u=fa[u][i]; if(u==v) return u; fd(i,Z,0) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i]; ed=v; return fa[u][0];}int main(){ freopen("light.in","r",stdin); freopen("light.out","w",stdout); int tp; scanf("%d %d",&n,&tp); fo(i,1,n){ scanf("%s",s+1); ln[i]=strlen(s+1); L[i]=tot+1,tot+=ln[i]; fo(j,L[i],L[i]+ln[i]-1) S[j]=ch(s[j-L[i]+1]); } fo(i,1,n) scanf("%d",&a[i]); fo(i,2,n){ int u,v; scanf("%d %d",&u,&v); T.link(u,v),T.link(v,u); } pre(1,0); tot=0,build(); fo(i,1,n){ add(pl[i],a[i]); add(pr[i],-a[i]); } int q; scanf("%d",&q); int ans=0; while(q--){ int op,x,y; scanf("%d %d %d",&op,&x,&y),x^=ans*tp,y^=ans*tp; if(op==1){ scanf("%s",s+1); if(dep[x]