前言：

其实之前就听说过这个算法，但是因为网上讲解的太少了，毕竟是个冷门算法，所以当时就没有去学习下去。昨天复习LCA的是时候看到有个题可以用这个算法，而且是特别裸的题，所以我就来学了。

参考blog:Kruskal重构树—学习笔记_niiick-CSDN博客_kruskal重构树

这个博客讲的挺好的，我就讲讲重点吧。

kruskal重构最重要的性质是：

LCA(u,v)的权值是 原图 u到v路径上最大/小边权的最小/大值(由建树时边权的排序方式决定)

kruskal一般用于解决这一类问题：

给你一个图，给你一个点，限制这个点不能走长度超过w的边，然后再问你一些问题。

这样讲可能有点抽象：

看一道kruskal经典题：

P4768 [NOI2018] 归程 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这道题很明显按降序先建kruskal重构树，因为低于某一海拔不能走了，也就是说明如果lca(u,v)<限制值，说明u走不到v，因为lca(u,v)是u->v路径上最小值的最大值。也就是说，当lca(u,v)>限制值，u能到达v。我们继续发现，我们让u往上爬，跑到一个祖先节点ff，如果ff>限制值，说明u能到达ff所在子树的所有节点，我们找到u的满足条件的最远祖先，那么这个点包含的节点就是u能走到的所有节点。于是再跑个最短路就行了。讲实话代码有点繁杂。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000010;
int n,m,lastans,cntx,totx,q,k,s;
int first[maxn],dep[maxn],ff[maxn][22],head[maxn],f[maxn];
struct 
{
    int l,a;
}p[maxn];
int dis[maxn],vis[maxn];
struct edge
{
    int v,w,a,u,nxt;
}e[maxn<<2];
struct edge1
{
    int v,w,a,u,nxt;
}t[maxn<<2],tr[maxn<<2];
void addx(int u,int v,int w)
{
    totx++;
    t[totx].v=v;
    t[totx].w=w;
    t[totx].nxt=head[u];
    head[u]=totx;
}
void add(int u,int v)
{
    cntx++;
    tr[cntx].v=v;
    tr[cntx].nxt=first[u];
    first[u]=cntx;
}
bool cmp(edge a,edge b)
{
    return a.a>b.a;
}
int find(int x){return (x==f[x])?x:f[x]=find(f[x]);}
void dfs(int u,int fa)
{
    dep[u]=dep[fa]+1;
    ff[u][0]=fa;
    for(int i=1;i<=20;i++)
    ff[u][i]=ff[ff[u][i-1]][i-1];
    for(int i=first[u];i;i=tr[i].nxt)
    {
        int v=tr[i].v;
        dfs(v,u);
        p[u].l=min(p[u].l,p[v].l);
    }
}
int query(int x,int y)
{
    for(int i=19;i>=0;i--) if(dep[x]-(1<<i)>0 && p[ff[x][i]].a>y) x=ff[x][i];
    return p[x].l;
}
void kruskal()
{
    int tot=0,cnt=n;
    for(int i=1;i<=(n<<1);i++) f[i]=i;
    sort(e+1,e+1+m,cmp);
    for(int i=1;i<=m;i++)
    {
        int u=e[i].u;
        int v=e[i].v;
        int fx=find(u);
        int fy=find(v);
        if(fx!=fy)
        {
            add(++cnt,fx);
            add(cnt,fy);
            f[fy]=f[fx]=cnt;
            p[cnt].a=e[i].a;
            tot++;
        }
        if(tot==n-1) break ;
    }
    dfs(cnt,0);
    while(q--)
    {
        int x1,x2;
        cin>>x1>>x2;
         int x=(k*lastans+x1-1)%n+1;
         int y=(k*lastans+x2)%(s+1);
    cout<<(lastans=query(x,y));
    cout<<endl;
    }
}
struct node
{
    int dis,id;
    bool operator < (const node &a) const
    {
        return dis>a.dis;
    }
};
priority_queue<node> qq;
void dij(int s)
{
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[s]=0; 
    node u;
    u.id=s;
    u.dis=0;
    qq.push(u);
    while(qq.size())
    {
        node u=qq.top();
        qq.pop();
        if(vis[u.id]) continue ;
        vis[u.id]=1;
        for(int i=head[u.id];i;i=t[i].nxt)
        {
            if(!vis[t[i].v] && dis[u.id]+t[i].w<dis[t[i].v])
            {
                dis[t[i].v]=dis[u.id]+t[i].w;
                qq.push(node{dis[t[i].v],t[i].v});
            }
        }
    }
    for(int i=1;i<=n;i++) p[i].l=dis[i];
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        lastans=0;
        cin>>n>>m;
        memset(e,0,sizeof(e));
        cntx=0;
        totx=0;
        memset(first,0,sizeof(first));
        memset(head,0,sizeof(head));
        memset(f,0,sizeof(f));
        for(int i=1;i<=m;i++) 
        {
            cin>>e[i].u>>e[i].v>>e[i].w>>e[i].a;
            addx(e[i].u,e[i].v,e[i].w);
            addx(e[i].v,e[i].u,e[i].w);
        }
        for(int i=n+1;i<=(n<<1);i++) p[i].l=0x3f3f3f3f;
        dij(1);
        cin>>q>>k>>s;
        kruskal();
    }   
    return 0;
}

View Code

再看一道经典题：P4197 Peaks - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这个就很裸了，第k大就是主席树呗（说的很简单，其实我不太会打主席树，所以我没打代码），然后就是个大水题。