自己搞了一个月的S(wen)A(hua)M(ke)，但是好像还是很白给
因为不会 (SA) 所以想想这题目怎么用 (SAM) 写
预处理显然，倍增跳后缀树维护出来每个点代表的 (a_i or b_i)，复杂度 (O((na+nb)log |S|))
如果能连接那么下一个串得是上一个串的限制的前缀
前缀就是反串的后缀
然后建反串的自动机，考虑在这上面得到的 (a o b) 的限制就可以变成 (a) 向 (b) 的子树里面建边了
那么因为是个树，所以有 (dfn) 序，所以线段树优化建图
具体而言就是每个 (a) 点往区间连边，点带权就完事了
写的时候要特别注意 (i or dfn[i])
但是这样的话会发现如果 (a_i) 和某个 (b_j) 倍增到同一个点上了
如果 $a and b $ 共点的时候两个 (len_age len_b) 就是完全可以转移的
那么我原来直接把 (a) 放到 (fa_{id}) 的方法就不奏效了
所以排序然后暴力扫，做前缀优化建图
具体就是按照长度把当前的点的 (a_{len},b_{len}) 排序，把树上的每个点拆成 (num_1) 和 (num_2)
父亲 (num_1) 连给 (b) ，(b) 连给满足条件的这点的 (a) 或者这个点自己的 (num_2)，(a) 只能往外连
然后拓扑即可
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define reg register
namespace yspm{
inline int read(){
int res=0,f=1; char k;
while(!isdigit(k=getchar())) if(k=='-') f=-1;
while(isdigit(k)) res=res*10+k-'0',k=getchar();
return res*f;
}
const int N=2e5+10,M=N<<1,SZ=M<<3;
int son[M][26],ed[N],len[M],fa[M],tot=1,las=1;
int va[N],vb[N],na,nb,slen,id1[N],id2[N],m,num,pre[M],suf[M];
inline void extend(int x,int id){
int tmp=las,np=las=++tot; ed[id]=np,len[np]=len[tmp]+1;
while(tmp&&!son[tmp][x]) son[tmp][x]=np,tmp=fa[tmp];
if(!tmp) return fa[np]=1,void();
int q=son[tmp][x]; if(len[q]==len[tmp]+1) return fa[np]=q,void();
int clone=++tot; fa[clone]=fa[q]; fa[np]=fa[q]=clone; len[clone]=len[tmp]+1;
for(reg int i=0;i<26;++i) son[clone][i]=son[q][i];
while(son[tmp][x]==q) son[tmp][x]=clone,tmp=fa[tmp];
return ;
}
struct Graph{
int head[SZ],cnt,f[SZ],in[SZ]; queue<int>q;
struct node{int to,nxt,dis;}e[SZ<<2];
inline void add(int u,int v,int w){
e[++cnt].to=v; e[cnt].nxt=head[u]; e[cnt].dis=w;
return head[u]=cnt,void();
}
inline int spfa(){
for(reg int i=1;i<=num;++i){
for(reg int j=head[i];j;j=e[j].nxt) in[e[j].to]++;
}
for(reg int i=1;i<=num;++i) if(!in[i]) q.push(i);
int ct=0,ans=0;
while(q.size()){
int fr=q.front(); q.pop(); ct++;
for(reg int i=head[fr];i;i=e[i].nxt){
int t=e[i].to; in[t]--;
f[t]=max(f[t],f[fr]+e[i].dis);
if(!in[t]) q.push(t);
}
} if(ct!=num) return -1;
for(reg int i=1;i<=num;++i) ans=max(ans,f[i]); return ans;
}
inline void clear(){
for(reg int i=1;i<=cnt;++i) e[i].nxt=e[i].to=e[i].dis=0;
for(reg int i=1;i<=num;++i) head[i]=f[i]=in[i]=0; cnt=0;
return ;
}
}G;
vector<pair<int,int> > g[SZ],h[SZ];
char s[N];
int bz[M][20],head[M],cnt; struct node{int to,nxt;}e[M];
inline void add(int u,int v){return e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt,void();}
inline void dfs(int x){
for(reg int i=1;i<=19;++i) bz[x][i]=bz[bz[x][i-1]][i-1];
for(reg int i=head[x];i;i=e[i].nxt) bz[e[i].to][0]=x,dfs(e[i].to);
return ;
}
inline int find(int l,int r){
int now=ed[l]; for(reg int i=19;~i;--i) if(len[bz[now][i]]>=r-l+1) now=bz[now][i];
return now;
}
inline void clear(){
G.clear();
for(reg int i=1;i<=slen;++i) ed[i]=0; num=0;
for(reg int i=1;i<=na;++i) va[i]=id1[i]=0;
for(reg int i=1;i<=nb;++i) vb[i]=id2[i]=0;
for(reg int i=1;i<=tot;++i){
memset(bz[i],0,sizeof(bz[i])); memset(son[i],0,sizeof(son[i]));
fa[i]=len[i]=head[i]=0; g[i].clear(),h[i].clear();
} las=tot=1; for(reg int i=1;i<=cnt;++i) e[i].nxt=e[i].to=0; cnt=0;
return ;
}
int tp[N];
inline void work(int i){
sort(g[i].begin(),g[i].end()); sort(h[i].begin(),h[i].end());
if(!g[i].size()){
for(auto p:h[i]) G.add(id2[p.second],suf[i],0);
return;
}
int now=0,sz=g[i].size();
for(reg int j=0,las=0;j<sz;++j,las=num){
tp[j]=++num,G.add(num,id1[g[i][j].second],g[i][j].first);
if(las) G.add(las,num,0);
} G.add(pre[i],tp[0],0);
for(auto p:h[i]){
while(now<sz&&p.first>g[i][now].first) now++;
if(now<sz) G.add(id2[p.second],tp[now],0);
G.add(id2[p.second],suf[i],0);
}
return ;
}
signed main(){
int T=read(); while(T--){
clear(); scanf("%s",s+1); slen=strlen(s+1);
for(reg int i=slen;i>=1;--i) extend(s[i]-'a',i);
for(reg int i=2;i<=tot;++i) add(fa[i],i); dfs(1);
na=read(); for(reg int i=1,tl,tr;i<=na;++i) tl=read(),tr=read(),va[i]=tr-tl+1,g[id1[i]=find(tl,tr)].push_back(make_pair(va[i],i));
nb=read(); for(reg int i=1,tl,tr;i<=nb;++i) tl=read(),tr=read(),vb[i]=tr-tl+1,h[id2[i]=find(tl,tr)].push_back(make_pair(vb[i],i));
for(reg int i=1;i<=na;++i) id1[i]=++num; for(reg int i=1;i<=nb;++i) id2[i]=++num;
m=read(); for(reg int i=1,ai,bi;i<=m;++i) ai=read(),bi=read(),G.add(id1[ai],id2[bi],0);
pre[1]=++num; suf[1]=++num; G.add(pre[1],suf[1],0); for(reg int i=2;i<=tot;++i) pre[i]=++num,suf[i]=++num;
for(reg int i=2;i<=tot;++i) G.add(suf[fa[i]],pre[i],0),G.add(pre[i],suf[i],0);
for(reg int i=1;i<=tot;++i) work(i);
printf("%lld
",G.spfa());
//exit(0);
}
return 0;
}
}
signed main(){return yspm::main();}