思路

在后缀树上进行一些操作就好了

后缀树上LCA的maxlen就是两个后缀的LCP的长度了

然后统计每个点作为LCA的次数和最大值、次大值、最小值、次小值

然后就做完了

代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #define int long longusing namespace std;int val[301000*2],n;char s[301000*2];namespace SAM{    int maxlen[301000*2],suflink[301000*2],trans[301000*2][26],endpos[301000*2],maxnum[301000*2],semaxnum[301000*2],minnum[301000*2],seminnum[301000*2],Nodecnt=1,in[301000*2],num[301000*2],maxval[301000*2];    int fir[301000*2],v[301000*2],nxt[301000*2],cnt=0;    void addedge(int ui,int vi){        ++cnt;        v[cnt]=vi;        nxt[cnt]=fir[ui];        fir[ui]=cnt;    }       int New_state(int _suflink,int *_trans,int _maxlen){        ++Nodecnt;        suflink[Nodecnt]=_suflink;        if(_trans)            for(int i=0;i<26;i++)                trans[Nodecnt][i]=_trans[i];        maxlen[Nodecnt]=_maxlen;                        return Nodecnt;    }    int add_len(int u,int c,int inq){        int z=New_state(0,NULL,maxlen[u]+1);        endpos[z]=1;        maxnum[z]=minnum[z]=inq;        semaxnum[z]=-0x3f3f3f3f;        seminnum[z]=0x3f3f3f3f;        while(u&&trans[u][c]==0){            trans[u][c]=z;            u=suflink[u];        }        if(!u){            suflink[z]=1;            return z;        }        int v=trans[u][c];        if(maxlen[v]==maxlen[u]+1){            suflink[z]=v;            return z;        }        int y=New_state(suflink[v],trans[v],maxlen[u]+1);        endpos[y]=0;        maxnum[y]=semaxnum[y]=-0x3f3f3f3f;        minnum[y]=seminnum[y]=0x3f3f3f3f;        suflink[z]=suflink[v]=y;        while(u&&trans[u][c]==v){            trans[u][c]=y;            u=suflink[u];        }        return z;    }    void insert(char *s,int len){        reverse(s+1,s+len+1);        reverse(val+1,val+len+1);        int last=1;        for(int i=1;i<=len;i++)            last=add_len(last,s[i]-'a',val[i]);    }    void build(void){        memset(num,0,sizeof(num));        memset(maxval,-0x3f,sizeof(maxval));        for(int i=1;i<=Nodecnt;i++)            addedge(suflink[i],i);    }    void dfs(int u){        for(int i=fir[u];i;i=nxt[i]){            dfs(v[i]);            num[maxlen[u]]+=endpos[u]*endpos[v[i]];            endpos[u]+=endpos[v[i]];            if(maxnum[v[i]]>=maxnum[u]){                if(max(maxnum[u],semaxnum[v[i]])>semaxnum[u])                    semaxnum[u]=max(maxnum[u],semaxnum[v[i]]);                maxnum[u]=maxnum[v[i]];            }            else if(maxnum[v[i]]>semaxnum[u]){                semaxnum[u]=maxnum[v[i]];            }            if(minnum[v[i]]<=minnum[u]){                if(min(seminnum[v[i]],minnum[u])
        
         1)            maxval[maxlen[u]]=max(maxval[maxlen[u]],max(maxnum[u]*semaxnum[u],minnum[u]*seminnum[u]));    }};signed main(){    scanf("%lld",&n);    scanf("%s",s+1);    for(int i=1;i<=n;i++)        scanf("%lld",&val[i]);    SAM::insert(s,n);    SAM::build();    SAM::dfs(1);    for(int i=n;i>=0;i--){        SAM::maxval[i]=max(SAM::maxval[i],SAM::maxval[i+1]);        SAM::num[i]+=SAM::num[i+1];    }    for(int i=0;i