考前挣扎（bu shi
之前留下来的坑
首先注意到 SAM的parent树 是反串的后缀树 也就是原串的前缀树
这个性质很重要 所以说我们在树上统计的时候两个点的lca就是两个后缀串的lcp 于是可以替代后缀数组（嘿嘿嘿
然后嘞我们树形dp 统计的size就是以这个串为前缀的子串个数
然后我们通过差分【最后后缀和 来进行统计对数
树形dp维护mn mx来进行查询最大 【有负所以要维护mn
这个最后还是要后缀max 但小心别把零转移过来
然后写写写 洛谷就过掉了
UOJ的hack数据真的吼2333
初始化的时候别忘了把0也清掉~
//Love and Freedom.#include#include #include #include #define mxn 1200000#define inf 2002122500#define ll long longusing namespace std;struct node{ int len,ch[26],fa,val,sz;}t[mxn];int lt,poi,rt;struct edge{int to,lt;}e[mxn];int in[mxn],cnt,a[mxn];void add(int x,int y){ e[++cnt].to=y; e[cnt].lt=in[x]; in[x]=cnt;}void insert(int c,int v){ int p = lt, np = lt = ++poi; t[np].len = t[p].len+1; t[np].val = v; t[np].sz = 1; for(;p && !t[p].ch[c]; p = t[p].fa) t[p].ch[c] = np; if(!p){t[np].fa = rt; return;} int q = t[p].ch[c]; if(t[q].len == t[p].len+1){t[np].fa = q;return;} int nq = ++poi; t[nq].len = t[p].len+1; memcpy(t[nq].ch,t[q].ch,sizeof(t[nq].ch)); t[nq].fa = t[q].fa; t[q].fa = t[np].fa = nq; for(;p && t[p].ch[c] == q; p = t[p].fa) t[p].ch[c] = nq;}void build(){ for(int i=2;i<=poi;i++) add(t[i].fa,i);}int mx[mxn],mn[mxn],sz[mxn],val[mxn];ll ans1[mxn],ans2[mxn];void dfs(int x){ sz[x] = t[x].sz; val[x] = t[x].val; if(sz[x]) mx[x] = mn[x] = val[x]; else mx[x] = -inf,mn[x] = inf; for(int i=in[x];i;i=e[i].lt) { int y = e[i].to; dfs(y); if(mn[x]!=inf && mn[y]!=inf) ans1[t[x].len] = max(ans1[t[x].len],max((ll)mn[x]*mn[y],(ll)mx[x]*mx[y])); ans2[t[x].len] += (ll)sz[x]*sz[y]; sz[x] += sz[y]; mx[x] = max(mx[x],mx[y]); mn[x] = min(mn[x],mn[y]); }}char ch[mxn];int main(){ int n; scanf("%d",&n); scanf("%s",ch+1); for(int i=1;i<=n;i++) scanf("%d",&a[i]); rt = lt = poi = 1; for(int i=n;i;i--) insert(ch[i]-'a',a[i]),ans1[i] = -(ll)inf*inf; ans1[0] = -(ll)inf*inf; build(); dfs(rt); for(int i=n;~i;i--) { ans2[i] += ans2[i+1]; if(ans2[i+1]) ans1[i] = max(ans1[i],ans1[i+1]); } for(int i=0;i