（题干中的废话已经划去）
dp显而易见
收益为负数的可以直接扔掉不管。不要一定更优
子串问题，考虑SAM
建立广义SAM
尝试匹配，匹配到的位置的parent树祖先如果有完整的串，那么可以从这个串转移
考虑祖先不好考虑
不妨考虑i对j(i<j)的贡献，就是子树了
线段树维护dfn序，区间对val取max
SAM学傻了
这个，由于是"完整出现”，所以AC自动机就可以（比广义SAM好写好调）
走一走属于第j个串的路径，对应的fail树的祖先包含i(i<j)的结束位置，那么可以转移
所以，同理，走完i之后，整个fail树子树的dp值和val取max
但是注意一点，根节点标号是0（反正我trie都这样写）
代码：
#include<bits/stdc++.h> #define il inline #define int long long #define reg register int #define mid ((l+r)>>1) #define numb (ch^'0') using namespace std; typedef long long ll; il void rd(int &x){ char ch;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x); } namespace Miracle{ const int N=300000+5; int n,m; struct node{ int nxt,to; }e[2*N]; int hd[N],cnt; void add(int x,int y){ e[++cnt].nxt=hd[x]; e[cnt].to=y; hd[x]=cnt; } char s[N],b[N]; int len[N],st[N]; ll v[N],f[N]; int dfn[N],dfn2[N]; int df; struct seg{ ll mx; ll tag; }t[4*N]; void pushup(int x){ t[x].mx=max(t[x<<1].mx,t[x<<1|1].mx); } void pushdown(int x){ if(t[x].tag<=0) return; t[x<<1].tag=max(t[x<<1].tag,t[x].tag); t[x<<1].mx=max(t[x<<1].mx,t[x].tag); t[x<<1|1].tag=max(t[x<<1|1].tag,t[x].tag); t[x<<1|1].mx=max(t[x<<1|1].mx,t[x].tag); t[x].tag=0; } void upda(int x,int l,int r,int L,int R,ll c){ if(L<=l&&r<=R){ t[x].mx=max(t[x].mx,c); t[x].tag=max(t[x].tag,c); return ; } pushdown(x); if(L<=mid) upda(x<<1,l,mid,L,R,c); if(mid<R) upda(x<<1|1,mid+1,r,L,R,c); pushup(x); } ll query(int x,int l,int r,int p){ if(l==r){ return t[x].mx; } pushdown(x); if(p<=mid) return query(x<<1,l,mid,p); else return query(x<<1|1,mid+1,r,p); } void cle(int x,int l,int r){ t[x].mx=0;t[x].tag=0; if(l==r) return; cle(x<<1,l,mid);cle(x<<1|1,mid+1,r); } struct AC{ int fail[N],ch[N][26]; int cnt; void ins(char *s,int l){ //int len=strlen(s+1); int now=0; for(reg i=1;i<=l;++i){ int c=s[i]-'a'; if(!ch[now][c]) ch[now][c]=++cnt; now=ch[now][c]; } } void build(){ queue<int>q; for(reg i=0;i<26;++i){ if(ch[0][i]) fail[ch[0][i]]=0,q.push(ch[0][i]); } while(!q.empty()){ int x=q.front();q.pop(); for(reg i=0;i<26;++i){ if(ch[x][i]){ fail[ch[x][i]]=ch[fail[x]][i]; q.push(ch[x][i]); } else ch[x][i]=ch[fail[x]][i]; } } for(reg i=1;i<=cnt;++i){ add(fail[i],i); } } void clear(){ memset(fail,0,sizeof fail); cnt=0; memset(ch,0,sizeof ch); } void dfs(int x){ dfn[x]=++df; for(reg i=hd[x];i;i=e[i].nxt){ int y=e[i].to; dfs(y); } dfn2[x]=df; } ll wrk(char *s,int l,int id){ ll ret=0; int now=0; for(reg i=1;i<=l;++i){ int c=s[i]-'a'; now=ch[now][c]; // cout<<"now "<<now<<" i "<<i<<" dfn "<<dfn[now]<<endl; ret=max(ret,query(1,1,df,dfn[now])); } // cout<<dfn[now]<<".. "<<dfn2[now]<<endl; upda(1,1,df,dfn[now],dfn2[now],ret+v[id]); return ret; } }ac; void clear(){ ac.clear(); if(df)cle(1,1,df); df=0;cnt=0; n=0; memset(hd,0,sizeof hd); } int main(){ //return 0; int t; rd(t); while(t--){ clear(); rd(m); int tot=0; for(reg i=1;i<=m;++i){ scanf("%s",b+1); scanf("%lld",&v[i]); st[i]=tot+1; len[i]=strlen(b+1); for(reg j=tot+1;j<=tot+len[i];++j){ s[j]=b[j-tot]; } tot=tot+len[i]; ac.ins(b,len[i]); } // cout<<" after ac.ins "<<endl; ac.build(); ac.dfs(0);//find dfn ll ans=0; // cout<<" let's wrk "<<endl; for(reg i=1;i<=m;++i){ // cout<<" ii "<<i<<"--------------------"<<v[i]<<" len "<<len[i]<<" st "<<st[i]<<endl; //if(v[i]<=0) continue; for(reg j=st[i];j<=st[i]+len[i]-1;++j){ b[j-st[i]+1]=s[j]; } // cout<<b+1<<endl; f[i]=ac.wrk(b,len[i],i)+v[i]; // cout<<i<<" : "<<f[i]<<endl; ans=max(ans,f[i]); } printf("%lld ",ans); } return 0; } } signed main(){ freopen("2963.in","r",stdin); freopen("2963.out","w",stdout); Miracle::main(); return 0; } /* Author: *Miracle* Date: 2019/2/3 11:36:24 */