旅行路线(route)

SAM裸题，只要把last变成父亲；

最后求一下不同子串个数；

ans = sigma len[i] - len[fa[i]];

#include<iostream>
#include<cstdio>
#include<map>
#include<queue>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
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;
}
/*
名利真吾事，纷然过眼休。人生能有死，天道未曾修
百战身皆朽，群心志已酬。一场无限业，何处可优游
*/
const int N = 1e6 + 1000,p1 = 1e9 + 7,p2 = 998244353;
int n,tot = 1,cnt; ll ans;
int head[N],du[N];
int id[N],len[N],fa[N],ci[N];
map<int,int> tr[N];
struct node{int nex,to;} a[N << 1];
void add(int f,int t)
{
    a[++ tot].nex = head[f];
    a[tot].to = t;
    head[f] = tot;
}

void insert(int x,int Q,int last)
{
    int np = ++ cnt,p = last,q,nq;
    len[np] = len[p] + 1; id[Q] = cnt;
    for(;p && tr[p].find(x) != tr[p].end();p = fa[p]) tr[p][x] = np;
    if(!p) fa[np] = 1;
    else if(len[q = tr[p][x]] == len[p] + 1) fa[np] = q;
    else
    {
        len[nq = ++ cnt] = len[p] + 1;
        fa[nq] = fa[q]; fa[q] = fa[np] = nq; tr[nq] = tr[q];
        for(;p;p = fa[p])
        {
            if(tr[p].find(x) == tr[p].end() || tr[p][x] != q) break;
            tr[p][x] = nq;
        }
    }
}

void dfs(int now,int fa)
{
    insert(du[now],now,id[fa]);
    for(int i = head[now],to;i;i = a[i].nex)
    {
        if(a[i].to == fa) continue;
        dfs(a[i].to,now);
    }
}

int main()
{
    freopen("route.in","r",stdin);
    freopen("route.out","w",stdout);
    cnt = id[0] = 1; n = read();
    for(int i = 1,x,y;i < n;i ++)
    {
        x = read(); y = read();
        du[x] ++; du[y] ++;
        add(x,y);
    }
    dfs(1,0);
    for(int i = 2;i <= cnt;i ++) ans += len[i] - len[fa[i]];
    printf("%lld\n",ans);
    fclose(stdin);fclose(stdout);
    return 0;
}