P4248 [AHOI2013]差异

Sunny_r · 2019-12-30 06:09:52 · 个人记录

据说反串建出来是后缀树，正着建树是前缀树，然而可能是因为我太团了，反正我并不知道为什么。。。

那么考虑题中的柿子，放到后缀树上就是两个后缀的最长公共前缀其实就是他们到根节点的公共路径的长度，所以我们可以联想到lca，所以原式的贡献就相当于两点之间的路径长度了，那么我们可以统计每条边的贡献来计算。

一条边的贡献是什么呢？

就是穿过这条边两端的siz乘积，所以也就是siz[x]*(n-siz[x])，而他的边权我们赋成什么呢，当然是len[x]-len[fa[x]]啦，不是要求路径长度嘛。

#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;
const int N = 1000005;
int fa[N], siz[N], tr[N][26], len[N], cnt = 1, last = 1, tot, head[N], n;
struct node{int to, nex, val;}a[N];
char s[N]; ll ans;
inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
    return x * f;
}
void add(int x, int y, int z) {a[++ tot].to = y; a[tot].val = z; a[tot].nex = head[x]; head[x] = tot;}
void insert(int x)
{
    int np = ++ cnt, p = last, nq, q; len[last = np] = len[p] + 1; siz[np] = 1;
    for(; p && !tr[p][x]; p = fa[p]) tr[p][x] = np;
    if(!p) fa[np] = 1;
    else
    {
        q = tr[p][x];
        if(len[q] == len[p] + 1) fa[np] = q;
        else
        {
            len[nq = ++ cnt] = len[p] + 1; fa[nq] = fa[q]; fa[q] = fa[np] = nq;
            memcpy(tr[nq], tr[q], sizeof(tr[q]));
            for(; p && tr[p][x] == q; p = fa[p]) tr[p][x] = nq;
        }
    }
}
void get_ans(int x)
{
    for(int i = head[x]; i; i = a[i].nex)
    {
        int y = a[i].to;
        get_ans(y); siz[x] += siz[y];
        ans += (ll)a[i].val * (n - siz[y]) * siz[y];
    }
    if(!siz[x]) siz[x] = 1;
}
void work()
{
    scanf("%s", s + 1); n = strlen(s + 1);
    for(int i = n; i >= 1; i --) insert(s[i] - 'a');
    for(int i = 2; i <= cnt; i ++) add(fa[i], i, len[i] - len[fa[i]]);
    get_ans(1); printf("%lld\n", ans);
}
int main() {return work(), 0; }