APIO2014回文串decription给定一个长度为\(n\)的字符串\(S\)。求其所有回文子串中出现次数乘上长度的最大值。\(n\leq3\times10^5\)solution根据经典结论，长度为\(n\)的字符串的本质不同回文子串个数不超过\(n\)个，我们可以找出所有本质不同回文子串，然后计算它们的

目录A.回文串B.序列分割C.连珠线A回文串给定字符串\(S\)。对\(S\)的所有回文子串，求其长度与出现次数之积的最大值。\(|S|\le300000\)。点击查看代码#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull

观察其实就是每个节点可以作为蓝线的中点一次，然后求蓝线的最大权值和。考虑如果是有根的话，可能是son[x]-x-fa[x]这种结构，也可能是son[x]-x-son[x]。应该可以用一个dp[i][0/

先说一下自己的SAM做法：看到回文串我们首先考虑对以下字符串建立SAM：正串+特殊字符1+特殊字符2+反串。这样也许能有一点用。晚上睡觉前我考虑的是对于正串的endpos在反串中

看到题之后第一想法就是斜率优化然后直接推式子了，却忽略了一个重要的前提就是和切的顺序无关，否则就应该是区间dp。（后怕）这里来证明一下：如果分成三段分别为\(s_1,s_2,s_3\)，