模板库

yuanzhiteng · 2023-10-20 15:58:53 · 个人记录

用于考前练习板子。

零. 目录

已经完成了的：

图论

树的直径

树的重心

最近公共祖先 Lca（倍增，Tarjan，树剖）

重链剖分

树上启发式合并 Dsu\ on\ tree

树哈希

最小生成树（Kruskal,Prim,Kruskal 重构树）

最短路（dijkstra,Floyd）（spfa 容易被卡，只用于判负环，差分约束会用到）

差分约束系统

同余最短路（待补充）

$Tarjan$ 求割点 $Tarjan$ 求点双联通分量 $Tarjan$ 求边双连通分量广义圆方树欧拉图，欧拉回路，欧拉路径二分图最大匹配（匈牙利，$Dinic$） - **字符串算法** $Manacher

kmp

失配树

exkmp

一. 图论

树的直径

here

/*知识点:树的直径*/
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int maxn = 1e4 + 5;

template <typename T>
inline void read(T& x){
x = 0; int f = 1; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -f; c=getchar();}
while(c >= '0' && c <= '9'){x = (x << 3) + (x << 1) + (c ^ 48),c = getchar(); } x *= f;
}
template <typename T,typename... Args>
inline void read(T &x, Args&... Arg){read(x),read(Arg...); }

int n;
int head[maxn],cnt;
struct Edge{
    int to,next,w;
}e[maxn << 1];
inline void add(int u,int v,int w){
    e[++cnt].to = v;
    e[cnt].w = w;
    e[cnt].next = head[u];
    head[u] = cnt;
}
int deep[maxn];
int pos,pos1,pos2;
inline void dfs(int u,int fa){
    if(deep[u] > deep[pos]) pos = u;
    for(int i=head[u];i;i=e[i].next){
        int v = e[i].to;
        if(v == fa) continue;
        deep[v] = deep[u] + e[i].w;
        dfs(v,u);
    }
}
int main(){

    read(n);
    for(int i=1;i<n;i++){
        int u,v;
        read(u,v);
        add(u,v,1);
        add(v,u,1);
    }
    dfs(1,0);
    pos1 = pos;
    deep[pos1] = 0;
    pos = 0;
    dfs(pos1,0);
    pos2 = pos;
    printf("%d\n",deep[pos2]);

    return 0;
}

树的重心

here

/*知识点:树的重心*/
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int maxn = 2e4 + 5;

template <typename T>
inline void read(T& x){
x = 0; int f = 1; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -f; c=getchar();}
while(c >= '0' && c <= '9'){x = (x << 3) + (x << 1) + (c ^ 48),c = getchar(); } x *= f;
}
template <typename T,typename... Args>
inline void read(T &x, Args&... Arg){read(x),read(Arg...); }

int T;
int n;
int head[maxn],cnt;
struct Edge{
    int to,next;
}e[maxn << 1];
inline void add(int u,int v){
    e[++cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt;
}
int dp[maxn],sz[maxn],root;
inline void dfs(int u,int fa){
    sz[u] = 1;
    for(int i=head[u];i;i=e[i].next){
        int v = e[i].to;
        if(v == fa) continue;
        dfs(v,u);
        sz[u] += sz[v];
        dp[u] = max(dp[u],sz[v]);
    }
    dp[u] = max(dp[u],n - sz[u]);
    if(dp[u] <= n / 2 && (!root || u < root))
        root = u;
}
inline void init(){
    cnt = root = 0;
    for(int i=1;i<=n;i++)   dp[i] = head[i] = 0;
}
int main(){

    read(T);
    while(T--){
        read(n);
        init();
        for(int i=1;i<n;i++){
            int u,v;
            read(u,v);
            add(u,v);
            add(v,u);
        }
        dfs(1,0);
        printf("%d %d\n",root,dp[root]);
    }

    return 0;
}

最近公共祖先 Lca

here

/*知识点:倍增lca*/
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int maxn = 5e5 + 5;

template <typename T>
inline void read(T& x){
x = 0; int f = 1; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -f; c=getchar();}
while(c >= '0' && c <= '9'){x = (x << 3) + (x << 1) + (c ^ 48),c = getchar(); } x *= f;
}
template <typename T,typename... Args>
inline void read(T &x, Args&... Arg){read(x),read(Arg...); }

int n,q,root;
int head[maxn],cnt;
struct Edge{
    int to,next;
}e[maxn << 1];
inline void add(int u,int v){
    e[++cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt;
}
int fa[maxn][20],deep[maxn];
inline void dfs(int u,int Fa){
    deep[u] = deep[Fa] + 1;
    fa[u][0] = Fa;
    for(int i=1;i<=18;i++)  
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for(int i=head[u];i;i=e[i].next){
        int v = e[i].to;
        if(v == Fa) continue;
        dfs(v,u);
    }
}
inline int lca(int u,int v){
    if(deep[u] < deep[v])   swap(u,v);
    for(int i=18;i>=0;i--)
        if(deep[fa[u][i]] >= deep[v])
            u = fa[u][i];
    if(u == v)  return u;
    for(int i=18;i>=0;i--)
        if(fa[u][i] != fa[v][i]){
            u = fa[u][i];
            v = fa[v][i];
        }
    return fa[u][0];
}
int main(){

    read(n,q,root);
    for(int i=1;i<n;i++){
        int u,v;
        read(u,v);
        add(u,v);
        add(v,u);
    }
    dfs(root,root);
    while(q--){
        int u,v;
        read(u,v);
        printf("%d\n",lca(u,v));
    }

    return 0;
}

/*知识点:Tarjan lca*/
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int maxn = 5e5 + 5;

template <typename T>
inline void read(T& x){
x = 0; int f = 1; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -f; c=getchar();}
while(c >= '0' && c <= '9'){x = (x << 3) + (x << 1) + (c ^ 48),c = getchar(); } x *= f;
}
template <typename T,typename... Args>
inline void read(T &x, Args&... Arg){read(x),read(Arg...); }

int n,q,root;
int head[maxn],cnt;
int qhead[maxn],qcnt;
struct Edge{
    int to,next;
}e[maxn << 1],qe[maxn << 1];
inline void add(int u,int v){
    e[++cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt;
}
inline void qadd(int u,int v){
    qe[++qcnt].to = v;
    qe[qcnt].next = qhead[u];
    qhead[u] = qcnt;
}
int fa[maxn];
inline int find(int x){
    if(x == fa[x])  return x;
    return fa[x] = find(fa[x]);
}
int lca[maxn << 1];
bool vis[maxn];
inline void Tarjan(int u){
    vis[u] = 1;
    for(int i=head[u];i;i=e[i].next){
        int v = e[i].to;
        if(vis[v])  continue;
        Tarjan(v);
        fa[v] = u;
    }
    for(int i=qhead[u];i;i=qe[i].next){
        int v = qe[i].to;
        if(vis[v]){
            lca[i] = find(v);
            if(i & 1)   lca[i + 1] = lca[i];
            else    lca[i - 1] = lca[i];
        }
    }
}
int main(){

    read(n,q,root);
    for(int i=1;i<=n;i++)   fa[i] = i;
    for(int i=1;i<n;i++){
        int u,v;
        read(u,v);
        add(u,v);
        add(v,u);
    }
    for(int i=1;i<=q;i++){
        int u,v;
        read(u,v);
        qadd(u,v);
        qadd(v,u);
    }
    Tarjan(root);
    for(int i=1;i<=q;i++)
        printf("%d\n",lca[i << 1]);

    return 0;
}

/*知识点:树剖lca*/
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int maxn = 5e5 + 5;

template <typename T>
inline void read(T& x){
x = 0; int f = 1; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -f; c=getchar();}
while(c >= '0' && c <= '9'){x = (x << 3) + (x << 1) + (c ^ 48),c = getchar(); } x *= f;
}
template <typename T,typename... Args>
inline void read(T &x, Args&... Arg){read(x),read(Arg...); }

int n,q,root;
int head[maxn],cnt;
struct Edge{
    int to,next;
}e[maxn << 1];
inline void add(int u,int v){
    e[++cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt;
}
int deep[maxn],sz[maxn],fa[maxn],Son[maxn];
inline void dfs1(int u,int fau){
    fa[u] = fau;
    sz[u] = 1;
    deep[u] = deep[fau] + 1;
    int son = -1;
    for(int i=head[u];i;i=e[i].next){
        int v = e[i].to;
        if(v == fau)    continue;
        dfs1(v,u);
        sz[u] += sz[v];
        if(sz[v] > son){
            Son[u] = v;
            son = sz[v];
        }
    }
}
int dfn[maxn],top[maxn];
int Time;
inline void dfs2(int u,int topu){
    top[u] = topu;
    dfn[u] = ++Time;
    if(!Son[u]) return;
    dfs2(Son[u],topu);
    for(int i=head[u];i;i=e[i].next){
        int v = e[i].to;
        if(v == fa[u] || v == Son[u])   continue;
        dfs2(v,v);
    }
}
inline int lca(int u,int v){
    while(top[u] != top[v]){
        if(deep[top[u]] < deep[top[v]]) swap(u,v);
        u = fa[top[u]];
    }
    if(deep[u] > deep[v])   swap(u,v);
    return u;
}
int main(){

    read(n,q,root);
    for(int i=1;i<n;i++){
        int u,v;
        read(u,v);
        add(u,v);
        add(v,u);
    }
    dfs1(root,root);
    dfs2(root,root);
    for(int i=1;i<=q;i++){
        int u,v;
        read(u,v);
        printf("%d\n",lca(u,v));
    }

    return 0;
}

重链剖分

here

/*知识点:重链剖分*/
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;

template <typename T>
inline void read(T& x){
x = 0; int f = 1; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -f; c=getchar();}
while(c >= '0' && c <= '9'){x = (x << 3) + (x << 1) + (c ^ 48),c = getchar(); } x *= f;
}
template <typename T,typename... Args>
inline void read(T &x, Args&... Arg){read(x),read(Arg...); }

int n,q,root;
ll mod;
int head[maxn],cnt;
struct Edge{
    int to,next;
}e[maxn << 1];
inline void add(int u,int v){
    e[++cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt;
}

inline void chadd(ll &x,ll y){
    x = (x + y) % mod;
}
int Idfn[maxn];
ll a[maxn];
struct Segment_Tree{
    struct Segment{
        ll val,tag;
    }tree[maxn << 2];
    inline int left(int x){
        return x << 1;
    }
    inline int right(int x){
        return x << 1 | 1;
    }
    inline void push_up(int p){
        tree[p].val = (tree[left(p)].val + tree[right(p)].val) % mod;
    }
    inline void get(int p,int l,int r,ll x){
        chadd(tree[p].val,x * (r - l + 1ll));
        chadd(tree[p].tag,x);
    }
    inline void push_down(int p,int l,int r){
        if(!tree[p].tag)    return;
        int mid = (l + r) >> 1;
        get(left(p),l,mid,tree[p].tag);
        get(right(p),mid + 1,r,tree[p].tag);
        tree[p].tag = 0;
    }
    inline void build(int p,int l,int r){
        if(l == r){
            tree[p].val = a[Idfn[l]] % mod;
            return;
        }
        int mid = (l + r) >> 1;
        build(left(p),l,mid);
        build(right(p),mid + 1,r);
        push_up(p);
    }
    inline void update(int p,int l,int r,int dl,int dr,ll x){
        if(dl <= l && dr >= r){
            chadd(tree[p].val,x * (r - l + 1ll));
            chadd(tree[p].tag,x);
            return;
        }
        push_down(p,l,r);
        int mid = (l + r) >> 1;
        if(dl <= mid)   update(left(p),l,mid,dl,dr,x);
        if(dr > mid)    update(right(p),mid + 1,r,dl,dr,x);
        push_up(p);
    }
    inline ll query(int p,int l,int r,int dl,int dr){
        if(dl <= l && dr >= r)  return tree[p].val;
        push_down(p,l,r);
        int mid = (l + r) >> 1;
        ll ret = 0;
        if(dl <= mid)   ret = query(left(p),l,mid,dl,dr);
        if(dr > mid)    chadd(ret,query(right(p),mid + 1,r,dl,dr));
        return ret;
    }
}seg;

int sz[maxn],deep[maxn],fa[maxn],Son[maxn];
inline void dfs1(int u,int fau){
    deep[u] = deep[fau] + 1;
    sz[u] = 1;
    fa[u] = fau;
    int son = -1;
    for(int i=head[u];i;i=e[i].next){
        int v = e[i].to;
        if(v == fau)    continue;
        dfs1(v,u);
        sz[u] += sz[v];
        if(sz[v] > son){
            Son[u] = v;
            son = sz[v];
        }
    }
}
int dfn[maxn],top[maxn];
int Time;
inline void dfs2(int u,int topu){
    top[u] = topu;
    dfn[u] = ++Time;
    Idfn[Time] = u;
    if(!Son[u]) return;
    dfs2(Son[u],topu);
    for(int i=head[u];i;i=e[i].next){
        int v = e[i].to;
        if(v == fa[u] || v == Son[u])   continue;
        dfs2(v,v);
    }
}
inline void update(int u,int v,ll x){
    while(top[u] != top[v]){
        if(deep[top[u]] < deep[top[v]]) swap(u,v);
        seg.update(1,1,n,dfn[top[u]],dfn[u],x);
        u = fa[top[u]];
    }   
    if(deep[u] < deep[v])   swap(u,v);
    seg.update(1,1,n,dfn[v],dfn[u],x);
}
inline ll query(int u,int v){
    ll ret = 0;
    while(top[u] != top[v]){
        if(deep[top[u]] < deep[top[v]]) swap(u,v);
        chadd(ret,seg.query(1,1,n,dfn[top[u]],dfn[u]));
        u = fa[top[u]];
    }
    if(deep[u] < deep[v])   swap(u,v);
    chadd(ret,seg.query(1,1,n,dfn[v],dfn[u]));
    return ret;
}
int main(){

    read(n,q,root,mod);
    for(int i=1;i<=n;i++)   read(a[i]);
    for(int i=1;i<n;i++){
        int u,v;
        read(u,v);
        add(u,v);
        add(v,u);
    }
    dfs1(root,root);
    dfs2(root,root);
    seg.build(1,1,n);
    int op,u,v;
    ll x;
    while(q--){
        read(op);
        if(op == 1){
            read(u,v,x);
            update(u,v,x);
        }
        else if(op == 2){
            read(u,v);
            printf("%lld\n",query(u,v));
        }
        else if(op == 3){
            read(u,x);
            seg.update(1,1,n,dfn[u],dfn[u] + sz[u] - 1,x);
        }
        else{
            read(u);
            printf("%lld\n",seg.query(1,1,n,dfn[u],dfn[u] + sz[u] - 1));
        }
    }

    return 0;
}

树上启发式合并 Dsu\ on\ tree

here

/*知识点:Dsu on tree*/
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int maxn = 1e5 + 5;

template <typename T>
inline void read(T& x){
x = 0; int f = 1; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -f; c=getchar();}
while(c >= '0' && c <= '9'){x = (x << 3) + (x << 1) + (c ^ 48),c = getchar(); } x *= f;
}
template <typename T,typename... Args>
inline void read(T &x, Args&... Arg){read(x),read(Arg...); }

int n,q;
int color[maxn];
int head[maxn],cnt;
struct Edge{
    int to,next;
}e[maxn << 1];
inline void add(int u,int v){
    e[++cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt;
}
int sz[maxn],Son[maxn],dfn[maxn],point[maxn];
int Time;
inline void dfs1(int u,int fa){
    sz[u] = 1;
    dfn[u] = ++Time;
    point[Time] = u;
    int son = -1;
    for(int i=head[u];i;i=e[i].next){
        int v = e[i].to;
        if(v == fa) continue;
        dfs1(v,u);
        sz[u] += sz[v];
        if(sz[v] > son){
            son = sz[v];
            Son[u] = v;
        }
    }
}
int tot;
int ans[maxn],colorcnt[maxn];
inline void Add(int x){
    if(!colorcnt[color[x]])  tot++;
    colorcnt[color[x]]++;
}
inline void Delete(int x){
    colorcnt[color[x]]--;
    if(!colorcnt[color[x]]) tot--;
}
inline void dfs2(int u,int fa,bool type){
    for(int i=head[u];i;i=e[i].next){
        int v = e[i].to;
        if(v == fa || v == Son[u])  continue;
        dfs2(v,u,0);
    }
    if(Son[u])  dfs2(Son[u],u,1);
    for(int i=head[u];i;i=e[i].next){
        int v = e[i].to;
        if(v == fa || v == Son[u])  continue;
        for(int i=dfn[v];i<=dfn[v]+sz[v]-1;i++)
            Add(point[i]);
    }
    Add(u);
    ans[u] = tot;
    if(!type)
        for(int i=dfn[u];i<=dfn[u]+sz[u]-1;i++)
            Delete(point[i]);
}
int main(){

    read(n);
    for(int i=1;i<n;i++){
        int u,v;
        read(u,v);
        add(u,v);
        add(v,u);
    }
    for(int i=1;i<=n;i++)   read(color[i]);

    dfs1(1,1);
    dfs2(1,1,1);

    read(q);
    while(q--){
        int u;
        read(u);
        printf("%d\n",ans[u]);
    }

    return 0;
}

树哈希

here

/*知识点:树哈希*/
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <random>
#include <chrono>
#include <map>
using namespace std;
typedef unsigned long long ull;
const int maxn = 55;

template <typename T>
inline void read(T& x){
x = 0; int f = 1; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -f; c=getchar();}
while(c >= '0' && c <= '9'){x = (x << 3) + (x << 1) + (c ^ 48),c = getchar(); } x *= f;
}
template <typename T,typename... Args>
inline void read(T &x, Args&... Arg){read(x),read(Arg...); }

int n,m;
int head[maxn],cnt;
struct Edge{
    int to,next;
}e[maxn << 1];
inline void add(int u,int v){
    e[++cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt;
}
int dp[maxn],sz[maxn],root[maxn][2];
inline void dfs(int u,int fa,int id){
    sz[u] = 1;
    dp[u] = 0;
    for(int i=head[u];i;i=e[i].next){
        int v = e[i].to;
        if(v == fa) continue;
        dfs(v,u,id);
        sz[u] += sz[v];
        dp[u] = max(dp[u],sz[v]);
    }
    dp[u] = max(dp[u],n - sz[u]);
    if(dp[u] <= n / 2){
        if(!root[id][0])    root[id][0] = u;
        else    root[id][1] = u;
    } 
}
ull Hash[maxn][maxn];
ull RealHash[maxn];
const ull mask = chrono::steady_clock::now().time_since_epoch().count();
inline ull XOR_SHIFT(ull x){
    x ^= mask;
    x ^= x << 13;
    x ^= x >> 7;
    x ^= x << 17;
    x ^= mask;
    return x;
}
inline void getHash(int u,int fa,int id){
    Hash[id][u] = 1;
    for(int i=head[u];i;i=e[i].next){
        int v = e[i].to;
        if(v == fa) continue;
        getHash(v,u,id);
        Hash[id][u] += XOR_SHIFT(Hash[id][v]);
    }
}
map<ull,int>vis;
inline void init(){
    cnt = 0;
    memset(head,0,sizeof(head));
}
int main(){

    read(m);
    for(int i=1;i<=m;i++){
        init();
        read(n);
        for(int j=1;j<=n;j++){
            int v;
            read(v);
            if(!v)  continue;
            add(j,v);
            add(v,j);
        }
        dfs(1,1,i);
        getHash(root[i][0],root[i][0],i);
        RealHash[i] = Hash[i][root[i][0]];
        if(root[i][1]){
            getHash(root[i][1],root[i][1],i);
            RealHash[i] = min(RealHash[i],Hash[i][root[i][1]]);
        }
    }
    for(int i=1;i<=m;i++){
        if(!vis[RealHash[i]]){
            vis[RealHash[i]] = i;
            printf("%d\n",i);
        }
        else
            printf("%d\n",vis[RealHash[i]]);
    }

    return 0;
}

最小生成树

/*知识点:kruskal最小生成树*/
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int maxn = 2e5 + 5;

template <typename T>
inline void read(T& x){
x = 0; int f = 1; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -f; c=getchar();}
while(c >= '0' && c <= '9'){x = (x << 3) + (x << 1) + (c ^ 48),c = getchar(); } x *= f;
}
template <typename T,typename... Args>
inline void read(T &x, Args&... Arg){read(x),read(Arg...); }

int n,m;
struct Edge{
    int u,v,w;
}e[maxn];
int fa[maxn];
inline int find(int x){
    if(x == fa[x])  return x;
    return fa[x] = find(fa[x]);
}
inline bool cmp(Edge x,Edge y){
    return x.w < y.w;
}
inline int kruskal(){
    sort(e + 1,e + 1 + m,cmp);
    int ret = 0,cnt = 0;
    for(int i=1;i<=m;i++){
        int u =e[i].u,v = e[i].v;
        int rootu = find(u),rootv = find(v);
        if(rootu == rootv)  continue;
        ret += e[i].w;
        cnt++;
        fa[rootu] = rootv;
    }
    if(cnt != n - 1){
        printf("orz\n");
        exit(0);
    }
    return ret;
}
int main(){

    read(n,m);
    for(int i=1;i<=n;i++)   fa[i] = i;
    for(int i=1;i<=m;i++)   read(e[i].u,e[i].v,e[i].w);
    printf("%d\n",kruskal());

    return 0;
}

/*知识点:Prim最小生成树*/
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <queue>
using namespace std;
const int maxn = 2e5 + 5;

template <typename T>
inline void read(T& x){
x = 0; int f = 1; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -f; c=getchar();}
while(c >= '0' && c <= '9'){x = (x << 3) + (x << 1) + (c ^ 48),c = getchar(); } x *= f;
}
template <typename T,typename... Args>
inline void read(T &x, Args&... Arg){read(x),read(Arg...); }

int n,m;
int head[maxn],cnt;
struct Edge{
    int to,next,w;
}e[maxn << 1];
inline void add(int u,int v,int w){
    e[++cnt].to = v;
    e[cnt].w = w;
    e[cnt].next = head[u];
    head[u] = cnt;
}
const int inf = 0x3f3f3f3f;
int dis[maxn];
struct node{
    int pos,dis;
    bool operator < (const node &x)const{
        return x.dis < dis;
    }
};
priority_queue<node>q;
bool vis[maxn];
inline void prim(){
    for(int i=1;i<=n;i++)   dis[i] = inf;
    dis[1] = 0;
    int edgecnt = 0,ret = 0;
    q.push((node){1,0});
    while(!q.empty() && edgecnt < n){               //注意一来就加了一条隐形的0边
        int u = q.top().pos,w = q.top().dis;
        q.pop();
        if(vis[u])  continue;
        vis[u] = 1;
        ret += w;
        edgecnt++;
        for(int i=head[u];i;i=e[i].next){
            int v = e[i].to;
            if(e[i].w < dis[v])
                dis[v] = e[i].w,q.push((node){v,dis[v]});
        }
    }
    if(edgecnt == n)    printf("%d\n",ret);         //注意一来就加了一条隐形的0边
    else    printf("orz\n");
}
int main(){

    read(n,m);
    for(int i=1;i<=m;i++){
        int u,v,w;
        read(u,v,w);
        add(u,v,w);
        add(v,u,w);
    }
    prim();

    return 0;
}

还有 Kruskal 重构树，看这道题。

最短路

```cpp /*知识点:dijkstra*/ #include <iostream> #include <stdio.h> #include <algorithm> #include <string.h> #include <queue> using namespace std; typedef long long ll; const int maxn = 2e5 + 5; template <typename T> inline void read(T& x){ x = 0; int f = 1; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -f; c=getchar();} while(c >= '0' && c <= '9'){x = (x << 3) + (x << 1) + (c ^ 48),c = getchar(); } x *= f; } template <typename T,typename... Args> inline void read(T &x, Args&... Arg){read(x),read(Arg...); } int n,m,start; int head[maxn],cnt; struct Edge{ int to,next; ll w; }e[maxn << 1]; inline void add(int u,int v,ll w){ e[++cnt].to = v; e[cnt].w = w; e[cnt].next = head[u]; head[u] = cnt; } struct node{ int pos; ll dis; bool operator < (const node &x)const{ return x.dis < dis; } }; priority_queue<node>q; bool vis[maxn]; ll dis[maxn]; const ll inf = 1e15; inline void dijkstra(int s){ for(int i=1;i<=n;i++) dis[i] = inf; dis[s] = 0; q.push((node){s,0}); while(!q.empty()){ int u = q.top().pos; q.pop(); if(vis[u]) continue; vis[u] = 1; for(int i=head[u];i;i=e[i].next){ int v = e[i].to; if(dis[v] > dis[u] + e[i].w){ dis[v] = dis[u] + e[i].w; if(!vis[v]) q.push((node){v,dis[v]}); } } } } int main(){ read(n,m,start); for(int i=1;i<=m;i++){ int u,v; ll w; read(u,v,w); add(u,v,w); } dijkstra(start); for(int i=1;i<=n;i++) printf("%lld ",dis[i]); return 0; } ``` $Floyd:$ [Here](https://www.luogu.com.cn/problem/B3647) ```cpp /*知识点:Floyd*/ #include <iostream> #include <stdio.h> #include <algorithm> #include <string.h> using namespace std; const int inf = 0x3f3f3f3f; const int maxn = 105; template <typename T> inline void read(T& x){ x = 0; int f = 1; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -f; c=getchar();} while(c >= '0' && c <= '9'){x = (x << 3) + (x << 1) + (c ^ 48),c = getchar(); } x *= f; } template <typename T,typename... Args> inline void read(T &x, Args&... Arg){read(x),read(Arg...); } int n,m; int dis[maxn][maxn]; inline void Floyd(){ for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]); } int main(){ read(n,m); memset(dis,inf,sizeof(dis)); for(int i=1;i<=m;i++){ int u,v,w; read(u,v,w); dis[u][v] = dis[v][u] = min(dis[u][v],w); } for(int i=1;i<=n;i++) dis[i][i] = 0; Floyd(); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++) printf("%d ",dis[i][j]); printf("\n"); } return 0; } ``` #### 差分约束系统 [here](https://www.luogu.com.cn/problem/P1993) ```cpp /*知识点:差分约束系统*/ #include <iostream> #include <stdio.h> #include <algorithm> #include <string.h> #include <queue> using namespace std; const int maxn = 5e3 + 5; template <typename T> inline void read(T& x){ x = 0; int f = 1; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -f; c=getchar();} while(c >= '0' && c <= '9'){x = (x << 3) + (x << 1) + (c ^ 48),c = getchar(); } x *= f; } template <typename T,typename... Args> inline void read(T &x, Args&... Arg){read(x),read(Arg...); } int n,m; int head[maxn],num; struct Edge{ int to,next,w; }e[100005]; queue<int>q; bool vis[maxn]; int cnt[maxn]; int dis[maxn]; const int inf = 0x3f3f3f3f; inline void spfa(int s){ for(int i=1;i<=n;i++) dis[i] = inf; dis[s] = 0,vis[s] = 1; q.push(s); while(!q.empty()){ int u = q.front(); q.pop(); vis[u] = 0; for(int i=head[u];i;i=e[i].next){ int v = e[i].to; if(dis[v] > dis[u] + e[i].w){ dis[v] = dis[u] + e[i].w; cnt[v] = cnt[u] + 1; if(cnt[v] > n){ printf("No\n"); return; } if(!vis[v]){ q.push(v); vis[v] = 1; } } } } printf("Yes\n"); return; } inline void add(int u,int v,int w){ e[++num].to = v; e[num].w = w; e[num].next = head[u]; head[u] = num; } int main(){ read(n,m); int op,a,b,c; for(int i=1;i<=m;i++){ read(op); if(op == 1){ read(a,b,c); add(a,b,-c); } else if(op == 2){ read(a,b,c); add(b,a,c); } else{ read(a,b); add(a,b,0); add(b,a,0); } } for(int i=1;i<=n;i++) add(0,i,0); //别忘了要建立超级源点防止不连通。 spfa(0); return 0; } ``` #### $Tarjan$ 求强连通分量 [here](https://www.luogu.com.cn/problem/B3609) ```cpp /*知识点:Tarjan 求强连通分量*/ #include <iostream> #include <stdio.h> #include <algorithm> #include <string.h> #include <vector> using namespace std; const int maxn = 1e5 + 5; template <typename T> inline void read(T& x){ x = 0; int f = 1; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -f; c=getchar();} while(c >= '0' && c <= '9'){x = (x << 3) + (x << 1) + (c ^ 48),c = getchar(); } x *= f; } template <typename T,typename... Args> inline void read(T &x, Args&... Arg){read(x),read(Arg...); } int n,m; int head[maxn],cnt; struct Edge{ int to,next; }e[maxn]; inline void add(int u,int v){ e[++cnt].to = v; e[cnt].next = head[u]; head[u] = cnt; } int dfn[maxn],low[maxn],color[maxn],sta[maxn]; int Time,scccnt,top; bool in_sta[maxn]; vector<int>scc[maxn]; inline void Tarjan(int u){ dfn[u] = low[u] = ++Time; sta[++top] = u,in_sta[u] = 1; for(int i=head[u];i;i=e[i].next){ int v = e[i].to; if(!dfn[v]){ Tarjan(v); low[u] = min(low[u],low[v]); } else if(in_sta[v]) low[u] = min(low[u],dfn[v]); } if(dfn[u] == low[u]){ ++scccnt; while(sta[top + 1] != u){ int x = sta[top--]; color[x] = scccnt; scc[scccnt].push_back(x); in_sta[x] = 0; } } } int main(){ read(n,m); for(int i=1;i<=m;i++){ int u,v; read(u,v); add(u,v); } for(int i=1;i<=n;i++) if(!dfn[i]){ top = 0; Tarjan(i); } printf("%d\n",scccnt); for(int i=1;i<=scccnt;i++) sort(scc[i].begin(),scc[i].end()); for(int i=1;i<=n;i++) if(!scc[color[i]].empty()){ for(auto x:scc[color[i]]) printf("%d ",x); printf("\n"); scc[color[i]].clear(); } return 0; } ``` #### $Tarjan$ 求割点 [here](https://www.luogu.com.cn/problem/P3388) ```cpp /*知识点:Tarjan 求割点*/ #include <iostream> #include <stdio.h> #include <algorithm> #include <string.h> using namespace std; const int maxn = 1e5 + 5; template <typename T> inline void read(T& x){ x = 0; int f = 1; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -f; c=getchar();} while(c >= '0' && c <= '9'){x = (x << 3) + (x << 1) + (c ^ 48),c = getchar(); } x *= f; } template <typename T,typename... Args> inline void read(T &x, Args&... Arg){read(x),read(Arg...); } int n,m; int head[maxn],cnt; struct Edge{ int to,next; }e[maxn << 1]; inline void add(int u,int v){ e[++cnt].to = v; e[cnt].next = head[u]; head[u] = cnt; } int dfn[maxn],low[maxn]; int Time; bool cut[maxn]; int tot; inline void Tarjan(int u,int root){ dfn[u] = low[u] = ++Time; int son = 0; for(int i=head[u];i;i=e[i].next){ int v = e[i].to; if(!dfn[v]){ Tarjan(v,root); if(u == root) son++; low[u] = min(low[u],low[v]); if(low[v] >= dfn[u] && u != root) cut[u] = 1; } else low[u] = min(low[u],dfn[v]); } if(u == root && son >= 2) cut[u] = 1; //特殊处理根节点 } int main(){ read(n,m); for(int i=1;i<=m;i++){ int u,v; read(u,v); add(u,v); add(v,u); } for(int i=1;i<=n;i++) if(!dfn[i]) Tarjan(i,i); for(int i=1;i<=n;i++) if(cut[i]) tot++; printf("%d\n",tot); for(int i=1;i<=n;i++) if(cut[i]) printf("%d ",i); return 0; } ``` #### $Tarjan$ 求点双联通分量 ```cpp /*知识点:Tarjan求点双*/ #include <iostream> #include <stdio.h> #include <algorithm> #include <string.h> #include <vector> using namespace std; const int maxn = 2e6 + 5; template <typename T> inline void read(T& x){ x = 0; int f = 1; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -f; c=getchar();} while(c >= '0' && c <= '9'){x = (x << 3) + (x << 1) + (c ^ 48),c = getchar(); } x *= f; } template <typename T,typename... Args> inline void read(T &x, Args&... Arg){read(x),read(Arg...); } int n,m; int head[maxn],cnt; struct Edge{ int to,next; }e[maxn << 1]; inline void add(int u,int v){ e[++cnt].to = v; e[cnt].next = head[u]; head[u] = cnt; } int dfn[maxn],low[maxn],sta[maxn]; int Time,top; int scccnt; vector<int>scc[maxn]; inline void Tarjan(int u,int fa){ dfn[u] = low[u] = ++Time; sta[++top] = u; int son = 0; for(int i=head[u];i;i=e[i].next){ int v = e[i].to; if(!dfn[v]){ Tarjan(v,u); low[u] = min(low[u],low[v]); son++; if(low[v] >= dfn[u]){ scccnt++; while(sta[top + 1] != v) scc[scccnt].push_back(sta[top--]); scc[scccnt].push_back(u); } } else low[u] = min(low[u],dfn[v]); } if(!fa && !son) scc[++scccnt].push_back(u); //特判孤立点 } int main(){ read(n,m); for(int i=1;i<=m;i++){ int u,v; read(u,v); add(u,v); add(v,u); } for(int i=1;i<=n;i++) if(!dfn[i]){ top = 0; Tarjan(i,0); } printf("%d\n",scccnt); for(int i=1;i<=scccnt;i++){ printf("%d ",(int)scc[i].size()); for(auto x:scc[i]) printf("%d ",x); printf("\n"); } return 0; } ``` #### $Tarjan$ 求双连通分量 ```cpp /*知识点:Tarjan 求边双*/ #include <iostream> #include <stdio.h> #include <algorithm> #include <string.h> #include <vector> using namespace std; const int maxn = 2e6 + 5; template <typename T> inline void read(T& x){ x = 0; int f = 1; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -f; c=getchar();} while(c >= '0' && c <= '9'){x = (x << 3) + (x << 1) + (c ^ 48),c = getchar(); } x *= f; } template <typename T,typename... Args> inline void read(T &x, Args&... Arg){read(x),read(Arg...); } int n,m; int head[maxn],cnt; struct Edge{ int to,next; }e[maxn << 1]; inline void add(int u,int v){ e[++cnt].to = v; e[cnt].next = head[u]; head[u] = cnt; } int dfn[maxn],low[maxn]; int Time; bool bridge[maxn << 1]; inline int Partner_Edge(int x){ if(x & 1) return x + 1; return x - 1; } inline void Tarjan(int u,int in_edge){ dfn[u] = low[u] = ++Time; for(int i=head[u];i;i=e[i].next){ int v = e[i].to; if(!dfn[v]){ Tarjan(v,i); low[u] = min(low[u],low[v]); if(low[v] > dfn[u]) bridge[i] = bridge[Partner_Edge(i)] = 1; } else if(i != Partner_Edge(in_edge)) low[u] = min(low[u],dfn[v]); } } vector<int>ecc[maxn]; int ecccnt; int color[maxn]; inline void dfs(int u,int col){ color[u] = col; ecc[col].push_back(u); for(int i=head[u];i;i=e[i].next){ int v = e[i].to; if(color[v] || bridge[i]) continue; dfs(v,col); } } int main(){ read(n,m); for(int i=1;i<=m;i++){ int u,v; read(u,v); add(u,v); add(v,u); } for(int i=1;i<=n;i++) if(!dfn[i]) Tarjan(i,0); for(int i=1;i<=n;i++) if(!color[i]) dfs(i,++ecccnt); printf("%d\n",ecccnt); for(int i=1;i<=ecccnt;i++){ printf("%d ",(int)ecc[i].size()); for(auto x:ecc[i]) printf("%d ",x); printf("\n"); } return 0; } ``` 可以用于缩点得到边双树。 #### 广义圆方树直接看这道题：[load压力](http://222.180.160.110:1024/contest/4027/problem/6)。 #### 欧拉图，欧拉回路，欧拉路径 [here](https://www.luogu.com.cn/problem/P7771) ```cpp /*知识点:Hierholzer法求欧拉回路/欧拉路径*/ #include <iostream> #include <stdio.h> #include <algorithm> #include <string.h> #include <vector> #define pii pair<int,int> #define mk make_pair using namespace std; const int maxn = 3e5 + 5; template <typename T> inline void read(T& x){ x = 0; int f = 1; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -f; c=getchar();} while(c >= '0' && c <= '9'){x = (x << 3) + (x << 1) + (c ^ 48),c = getchar(); } x *= f; } template <typename T,typename... Args> inline void read(T &x, Args&... Arg){read(x),read(Arg...); } int n,m; int in[maxn],out[maxn]; vector<pii>G[maxn]; inline void add(int u,int v,int id){ G[u].push_back(mk(v,id)); in[v]++,out[u]++; } int cur[maxn],sta[maxn]; int top; bool vis[maxn]; inline void dfs(int u){ for(int i=cur[u];i<(int)G[u].size();i=cur[u]){ //注意不是i++,不然会T cur[u] = i + 1; int v = G[u][i].first,id = G[u][i].second; if(vis[id]) continue; vis[id] = 1; dfs(v); } sta[++top] = u; } int main(){ read(n,m); for(int i=1;i<=m;i++){ int u,v; read(u,v); add(u,v,i); } int S = 0,num = 0; for(int i=1;i<=n;i++) if(in[i] != out[i]){ num++; if(num > 2){ printf("No\n"); return 0; } if(out[i] - in[i] == 1) S = i; } for(int i=1;i<=n;i++) sort(G[i].begin(),G[i].end()); if(!S) S = 1; //可能存在欧拉回路,导致所有的in=out,此时贪心将起点设为1即可 dfs(S); for(int i=top;i>=1;i--) printf("%d ",sta[i]); return 0; } ``` #### 二分图最大匹配（匈牙利，$Dinic$） [here](https://www.luogu.com.cn/problem/P3386) ```cpp /*知识点:匈牙利算法求二分图最大匹配*/ #include <iostream> #include <stdio.h> #include <algorithm> #include <string.h> using namespace std; const int maxn = 5e4 + 5; template <typename T> inline void read(T& x){ x = 0; int f = 1; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -f; c=getchar();} while(c >= '0' && c <= '9'){x = (x << 3) + (x << 1) + (c ^ 48),c = getchar(); } x *= f; } template <typename T,typename... Args> inline void read(T &x, Args&... Arg){read(x),read(Arg...); } int nl,nr,m; int head[maxn],cnt; struct Edge{ int to,next; }e[maxn]; inline void add(int u,int v){ e[++cnt].to = v; e[cnt].next = head[u]; head[u] = cnt; } int vis[maxn]; int match[maxn]; inline bool dfs(int u,int dfn){ for(int i=head[u];i;i=e[i].next){ int v = e[i].to; if(vis[v] == dfn) continue; vis[v] = dfn; if(!match[v] || dfs(match[v],dfn)){ match[v] = u; return 1; } } return 0; } int main(){ read(nl,nr,m); for(int i=1;i<=m;i++){ int u,v; read(u,v); v += nl; add(u,v); } int ans = 0; for(int i=1;i<=nl;i++) if(dfs(i,i)) ans++; printf("%d\n",ans); return 0; } ``` ```cpp /*知识点:Dinic求二分图最大匹配*/ #include <iostream> #include <stdio.h> #include <algorithm> #include <string.h> #include <queue> using namespace std; const int maxn = 1e5 + 5; const int inf = 0x3f3f3f3f; template <typename T> inline void read(T& x){ x = 0; int f = 1; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -f; c=getchar();} while(c >= '0' && c <= '9'){x = (x << 3) + (x << 1) + (c ^ 48),c = getchar(); } x *= f; } template <typename T,typename... Args> inline void read(T &x, Args&... Arg){read(x),read(Arg...); } int nl,nr,n,m; int S,T; int head[maxn],cnt; struct Edge{ int to,next,w; }e[maxn << 1]; inline void add(int u,int v,int w){ e[++cnt].to = v; e[cnt].w = w; e[cnt].next = head[u]; head[u] = cnt; } int cur[maxn],deep[maxn]; queue<int>q; inline bool bfs(){ for(int i=1;i<=n;i++) deep[i] = 0; deep[S] = 1; while(!q.empty()) q.pop(); q.push(S); while(!q.empty()){ int u = q.front(); q.pop(); for(int i=head[u];i;i=e[i].next){ int v = e[i].to; if(!deep[v] && e[i].w){ deep[v] = deep[u] + 1; q.push(v); if(v == T) return 1; } } } return 0; } inline int broedge(int x){ if(x & 1) return x + 1; return x - 1; } inline int dfs(int u,int flow){ if(u == T) return flow; int rest = flow; for(int i=cur[u];i&&rest;i=e[i].next){ cur[u] = i; int v = e[i].to,w = e[i].w; if(deep[v] == deep[u] + 1 && w){ int sum = dfs(v,min(rest,w)); if(!sum) deep[v] = 0; e[i].w -= sum; e[broedge(i)].w += sum; rest -= sum; } } return flow - rest; } inline int Dinic(){ int ret = 0,flow; while(bfs()){ for(int i=1;i<=n;i++) cur[i] = head[i]; while((flow = dfs(S,inf))) ret += flow; } return ret; } int main(){ read(nl,nr,m); for(int i=1;i<=m;i++){ int u,v; read(u,v); v += nl; add(u,v,1); add(v,u,0); } n = nl + nr + 2; S = n - 1,T = n; for(int i=1;i<=nl;i++) add(S,i,1),add(i,S,0); for(int i=1;i<=nr;i++) add(i + nl,T,1),add(T,i + nl,0); printf("%d\n",Dinic()); return 0; } ``` *** ### 二. 字符串算法 #### $Manacher

here

/*知识点:Manacher*/
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int maxn = 22000005;

template <typename T>
inline void read(T& x){
x = 0; int f = 1; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -f; c=getchar();}
while(c >= '0' && c <= '9'){x = (x << 3) + (x << 1) + (c ^ 48),c = getchar(); } x *= f;
}
template <typename T,typename... Args>
inline void read(T &x, Args&... Arg){read(x),read(Arg...); }

int r[maxn],len;
int s[maxn];
inline void Manacher(char *c){
    len = strlen(c + 1);
    for(int i=1;i<=len;i++){
        s[i << 1] = c[i];
        s[(i << 1) - 1] = '#';
    }
    len = len << 1 | 1;
    s[len] = '#';

    int R = 0,pos = 0,pre = 0;
    for(int i=1;i<=len;i++){
        if(i > R){
            while(i + r[i] <= len && i - r[i] >= 1 && s[i + r[i]] == s[i - r[i]])   r[i]++;
            r[i]--;
            if(i + r[i] > R)    R = i + r[i],pos = i;
        }
        else{
            pre = (pos << 1) - i;
            if(pre - r[pre] > pos - r[pos]) r[i] = r[pre];
            else if(pre - r[pre] < pos - r[pos]) r[i] = pos + r[pos] - i;
            else{
                r[i] = pos + r[pos] - i;
                while(i + r[i] <= len && i - r[i] >= 1 && s[i + r[i]] == s[i - r[i]])   r[i]++;
                r[i]--;
            } 
            if(i + r[i] > R)    R = i + r[i],pos = i;
        }
    }
}
char c[maxn];
int main(){

    scanf("%s",c + 1);
    Manacher(c);
    int ans = 0;
    for(int i=1;i<=len;i++) ans = max(ans,r[i]);
    printf("%d\n",ans);

    return 0;
}

kmp

here

/*知识点:kmp*/
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int maxn = 2e6 + 5;

template <typename T>
inline void read(T& x){
x = 0; int f = 1; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -f; c=getchar();}
while(c >= '0' && c <= '9'){x = (x << 3) + (x << 1) + (c ^ 48),c = getchar(); } x *= f;
}
template <typename T,typename... Args>
inline void read(T &x, Args&... Arg){read(x),read(Arg...); }

int border[maxn];
char s1[maxn],s2[maxn],inp[maxn];
inline void kmp(char *s){
    int len = strlen(s + 1);
    for(int i=2;i<=len;i++){
        int pre = border[i - 1];
        while(pre && s[pre + 1] != s[i])    pre = border[pre];
        if(pre) border[i] = pre + 1;
        else if(s[1] == s[i])   border[i] = 1;
    }
}
int main(){

    scanf("%s",s1 + 1);
    scanf("%s",s2 + 1);
    int len1 = strlen(s1 + 1),len2 = strlen(s2 + 1);
    for(int i=1;i<=len2;i++)    inp[i] = s2[i];
    inp[len2 + 1] = '#';
    for(int i=1;i<=len1;i++)    inp[i + len2 + 1] = s1[i];
    kmp(inp);
    for(int i=len2+2;i<=len1+len2+1;i++)
        if(border[i] == len2)   printf("%d\n",i - len2 * 2);
    for(int i=1;i<=len2;i++)    border[i] = 0;
    kmp(s2);
    for(int i=1;i<=len2;i++)    printf("%d ",border[i]);

    return 0;
}

失配树（Fail 树）

here

/*知识点:kmp,失配树*/
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int maxn = 1e6 + 5;

template <typename T>
inline void read(T& x){
x = 0; int f = 1; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -f; c=getchar();}
while(c >= '0' && c <= '9'){x = (x << 3) + (x << 1) + (c ^ 48),c = getchar(); } x *= f;
}
template <typename T,typename... Args>
inline void read(T &x, Args&... Arg){read(x),read(Arg...); }

int border[maxn],len;
char c[maxn];
inline void kmp(char *s){
    len = strlen(s + 1);
    for(int i=2;i<=len;i++){
        int pre = border[i - 1];
        while(pre && s[i] != s[pre + 1])    pre = border[pre];
        if(pre) border[i] = pre + 1;
        else if(s[i] == s[1])   border[i] = 1;
    }
}
int head[maxn],cnt;
struct Edge{
    int to,next;
}e[maxn << 1];
inline void add(int u,int v){
    e[++cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt;
}
inline void build(){
    for(int i=1;i<=len;i++){
        add(i + 1,border[i] + 1);
        add(border[i] + 1,i + 1);
    }
}
int fa[maxn][25],deep[maxn];
inline void dfs(int u,int Fa){
    deep[u] = deep[Fa] + 1;
    fa[u][0] = Fa;
    for(int i=1;i<=20;i++)  fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for(int i=head[u];i;i=e[i].next){
        int v = e[i].to;
        if(v == Fa) continue;
        dfs(v,u);
    }
}
inline int lca(int u,int v){
    if(deep[u] < deep[v])   swap(u,v);
    for(int i=20;i>=0;i--)
        if(deep[fa[u][i]] >= deep[v])
            u = fa[u][i];
    if(u == v)  return u;
    for(int i=20;i>=0;i--)
        if(fa[u][i] != fa[v][i]){
            u = fa[u][i];
            v = fa[v][i];
        }
    return fa[u][0];
}
int q;
int main(){

    scanf("%s",c + 1);
    kmp(c);
    build();
    dfs(1,0);
    read(q);
    while(q--){
        int u,v;
        read(u,v);
        u++,v++;
        int Lca = lca(u,v);
        if(deep[u] > deep[v])   swap(u,v);
        if(Lca == u)    Lca = fa[Lca][0];
        printf("%d\n",Lca - 1);
    }

    return 0;
}

exkmp

here

/*知识点:exkmp*/
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
typedef long long ll;
const int maxn = 4e7 + 5;

template <typename T>
inline void read(T& x){
x = 0; int f = 1; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -f; c=getchar();}
while(c >= '0' && c <= '9'){x = (x << 3) + (x << 1) + (c ^ 48),c = getchar(); } x *= f;
}
template <typename T,typename... Args>
inline void read(T &x, Args&... Arg){read(x),read(Arg...); }

int lcp[maxn];
char a[maxn],b[maxn],c[maxn];
inline void exkmp(char *s){
    int len = strlen(s + 1);
    int R = 0,pos = 0;
    for(int i=2;i<=len;i++){
        if(i > R){
            while(i + lcp[i] <= len && s[i + lcp[i]] == s[lcp[i] + 1])  lcp[i]++;
            if(i + lcp[i] - 1 > R)  R = i + lcp[i] - 1,pos = i;
        }
        else{
            if(lcp[i - pos + 1] < R - i + 1) lcp[i] = lcp[i - pos + 1];
            else{
                lcp[i] = R - i + 1;
                while(i + lcp[i] <= len && s[i + lcp[i]] == s[lcp[i] + 1])  lcp[i]++;
            }
            if(i + lcp[i] - 1 > R)  R = i + lcp[i] - 1,pos = i;
        }
    }
}
int main(){

    scanf("%s",a + 1);
    scanf("%s",b + 1);
    int lena = strlen(a + 1),lenb = strlen(b + 1);
    exkmp(b);
    ll ans = 0;
    lcp[1] = lenb;
    for(int i=1;i<=lenb;i++)   ans ^= i * 1ll * (lcp[i] + 1ll);
    printf("%lld\n",ans);

    for(int i=1;i<=lenb;i++)    c[i] = b[i],lcp[i] = 0;
    c[lenb + 1] = '#';
    for(int i=1;i<=lena;i++)    c[i + lenb + 1] = a[i];
    exkmp(c);
    ans = 0;
    for(int i=lenb+2;i<=lena+lenb+1;i++)   ans ^= (i - lenb - 1) * 1ll * (lcp[i] + 1ll);
    printf("%lld\n",ans);

    return 0;
}