题目链接：
学了后缀自动机之后再来写这道题就轻松多了……
首先，题面中的两杯酒\(r\)相似就是这两个后缀的最长公共前缀大于等于\(r\)。把串翻转过来之后就变成了两个前缀的最长公共后缀……然后就是\(parent\)树的事了……
接着，我们要求出选出两杯\(r\)相似的酒的方案数。这个比较显然，就是枚举两个节点的\(lca\)，然后把儿子的\(right\)集合大小 两两乘起来就可以了。
然后就是选出两个值使得乘积最大。树型\(dp\)还是比较显然的，在\(parent\)树上记录一下每棵子树内的最大值、最小值，那么显然最大值要么就是最大值和最大值乘起来，要么就是最小值和最小值乘起来，要么就是子树内的最大值。背包一下就求出来了。由于这道题每次是更新一段前缀，于是把更新弄成点事件，\(dp\)完后再从大到小扫一遍即可。要注意负数的情况。
下面贴代码：
#include#include #include #include #include #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)#define maxn 600010#define INF (1LL<<61)#define maxint (1<<30)using namespace std;typedef long long llg;char s[maxn>>1];int n,tot,la,head[maxn],next[maxn],to[maxn],tt,a[maxn],nn;int son[maxn][26],len[maxn],fa[maxn],siz[maxn],pos[maxn];llg ans[maxn],maxv[maxn],minv[maxn],f[maxn],c[maxn];int getint(){ int w=0;bool q=0; char c=getchar(); while((c>'9'||c<'0')&&c!='-') c=getchar(); if(c=='-') c=getchar(),q=1; while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;}void link(int x,int y){to[++tt]=y;next[tt]=head[x];head[x]=tt;}void insert(int p,int x){ int np=++tot; siz[np]=1; len[np]=len[p]+1; pos[np]=a[++nn]; f[np]=-INF; for(;p && !son[p][x];p=fa[p]) son[p][x]=np; if(!p) fa[np]=1; else{ int q=son[p][x]; if(len[q]==len[p]+1) fa[np]=q; else{ int nq=++tot; memcpy(son[nq],son[q],sizeof(son[q])); fa[nq]=fa[q]; fa[np]=fa[q]=nq; len[nq]=len[p]+1; for(;son[p][x]==q;p=fa[p]) son[p][x]=nq; } } la=np;}void dfs(int u){ if(siz[u]) maxv[u]=minv[u]=pos[u]; for(int i=head[u],v;v=to[i],i;i=next[i]){ dfs(v); ans[len[u]]+=(llg)siz[u]*siz[v]; if(siz[u]) f[u]=max(f[u],max(maxv[u]*maxv[v],minv[u]*minv[v])); maxv[u]=max(maxv[u],maxv[v]); minv[u]=min(minv[u],minv[v]); siz[u]+=siz[v]; f[u]=max(f[u],f[v]); } if(siz[u]>1) c[len[u]]=max(c[len[u]],f[u]);}int main(){ File("a"); scanf("%d",&n); scanf("%s",s+1); tot=la=1; for(int i=1;i<=n;i++) a[n-i+1]=getint(); for(int i=n>>1;i;i--) swap(s[i],s[n-i+1]); for(int i=1;i<=n;i++) insert(la,s[i]-'a'); for(int i=0;i<=n;i++) c[i]=-INF; for(int i=2;i<=tot;i++) link(fa[i],i); for(int i=1;i<=tot;i++) minv[i]=maxint,maxv[i]=-maxint,f[i]=-INF; dfs(1); for(int i=n-1;i>=0;i--) c[i]=max(c[i],c[i+1]),ans[i]+=ans[i+1]; for(int i=0;i