「雅礼集训 2017 Day7」事情的相似度

我们先将字符串建后缀自动机。然后对于两个前缀\([1,i]\)，\([1,j]\)，他们的最长公共后缀长度就是他们在\(fail\)树上对应节点的\(lca\)的\(maxlen\)。

所以现在问题就变成了一个树上问题：给定一棵树，每个点有一个权值\((mxlen)\)，询问编号在一段区间内的点两两之间\(lca\)权值的最大值。

方法很多，这里用的\(dsu\ on\ tree\)。对于每个点\(v\)，我们计算其作为\(lca\)的贡献。显然贡献的情况是一个点对，他们在\(v\)的不同子树中(\(v\)自己也算一个子树)。但是这样点对的数量可能达到\(O(n^2)\)。

不过我们仔细思考一下就会发现，其实这样的点对不多。对于一个\(lca\)，一个子节点\(v\)，我们要与一个在之前已经加入的节点，我们发现，根据贪心，只需要与\(v\)的前驱和后继组合就可以了。

代码：

#include
    
     #define ll long long#define N 200005using namespace std;inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}int n,m;char s[N];int ch[N<<1][2],fail[N<<1],mxlen[N<<1];int id[N<<1];int cnt=1,last=1;void Insert(int f,int i) {    static int now,p;    now=++cnt;    p=last,last=now;    id[now]=i;    mxlen[now]=mxlen[p]+1;    while(p&&!ch[p][f]) ch[p][f]=now,p=fail[p];    if(!p) return fail[now]=1,void();        int q=ch[p][f];    if(mxlen[q]==mxlen[p]+1) return fail[now]=q,void();        int New=++cnt;    memcpy(ch[New],ch[q],sizeof(ch[q]));    fail[New]=fail[q];    fail[q]=fail[now]=New;    mxlen[New]=mxlen[p]+1;    while(p&&ch[p][f]==q) ch[p][f]=New,p=fail[p];}struct load {int to,next;}e[N<<2];int h[N<<1],edge=1;void add(int i,int j) {e[++edge]=(load) {j,h[i]};h[i]=edge;}int val[N<<1];int size[N<<1],son[N<<1];void dfs(int v) {    size[v]=1;    for(int i=h[v];i;i=e[i].next) {        int to=e[i].to;        dfs(to);        size[v]+=size[to];        if(size[son[v]]