解法一【后缀树+树形dp】见【这里】。
把后缀数组中的元素按height从大到小合并并在合并的过程中统计答案，用并查集维护集合，记录大小和最值。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
const int maxn=1000010;
const LL oo=5e18;
char s[maxn];
int sa[maxn],rank[maxn],height[maxn],cnt[maxn],f[maxn],
a[maxn],fa[maxn],que[maxn],
n;
LL size[maxn],mn1[maxn],mn2[maxn],mx1[maxn],mx2[maxn],num[maxn],ans[maxn];
int cmp(int x,int y)
{return height[x]>height[y];
}
int find(int x)
{return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main()
{int m=26,p,x,y;scanf("%d",&n);scanf("%s",s+1);for (int i=1;i<=n;i++) scanf("%d",&a[i]);for (int i=1;i<=n;i++) cnt[rank[i]=s[i]-'a'+1]++;for (int i=2;i<=m;i++) cnt[i]+=cnt[i-1];for (int i=n;i;i--) sa[cnt[rank[i]]--]=i;for (int k=1;;k<<=1){p=0;for (int i=n-k+1;i<=n;i++) f[++p]=i;for (int i=1;i<=n;i++)if (sa[i]>k) f[++p]=sa[i]-k;for (int i=1;i<=m;i++) cnt[i]=0;for (int i=1;i<=n;i++) cnt[rank[f[i]]]++;for (int i=2;i<=m;i++) cnt[i]+=cnt[i-1];for (int i=n;i;i--) sa[cnt[rank[f[i]]]--]=f[i];for (int i=1;i<=n;i++) f[i]=rank[i];rank[sa[1]]=1;for (int i=2;i<=n;i++)if (f[sa[i]]==f[sa[i-1]]&&f[sa[i]+k]==f[sa[i-1]+k])rank[sa[i]]=rank[sa[i-1]];else rank[sa[i]]=rank[sa[i-1]]+1;m=rank[sa[n]];if (m>=n) break;}for (int i=1;i<=n;i++){if (height[rank[i]]=height[rank[i-1]]) height[rank[i]]--;while (s[i+height[rank[i]]]==s[sa[rank[i]-1]+height[rank[i]]]) height[rank[i]]++;}for (int i=1;i<n;i++) que[i]=i+1;sort(que+1,que+n,cmp);for (int i=1;i<=n;i++){fa[i]=i;size[i]=1;mx1[i]=mn1[i]=a[i];mx2[i]=-oo;mn2[i]=oo;}for (int i=1;i<n;i++) ans[i]=-oo;for (int i=1;i<n;i++){x=find(sa[que[i]]);y=find(sa[que[i]-1]);num[height[que[i]]]+=size[x]*size[y];size[x]+=size[y];if (mn1[y]<=mn1[x]){mn2[x]=mn1[x];mn1[x]=mn1[y];mn2[x]=min(mn2[x],mn2[y]);}else mn2[x]=min(mn2[x],mn1[y]);if (mx1[y]>=mx1[x]){mx2[x]=mx1[x];mx1[x]=mx1[y];mx2[x]=max(mx2[x],mx2[y]);}else mx2[x]=max(mx2[x],mx1[y]);fa[y]=x;ans[height[que[i]]]=max(ans[height[que[i]]],max(mx1[x]*mx2[x],mn1[x]*mn2[x]));}for (int i=n-2;i>=0;i--){ans[i]=max(ans[i],ans[i+1]);num[i]+=num[i+1];}for (int i=0;i<n;i++) printf("%lld %lld\n",num[i],ans[i]==-oo?0:ans[i]);
}