由于我的语文太菜了阅读本文章之前请小心断句

学习kruskal重构树的前置知识：

kruskal算法

并查集

树上倍增/Tarjan求lca

kruskal重构树基于kruskal算法，能巧妙地求解询问从A点走到B点的所有路径中，最长的边最小值是多少，或者最短的边的最大值之类的问题。

这个东西的本质其实就是把最小生成树上的边权改成了点权，原图的节点会增加n-1个，也会多出一些神奇性质。

以下是性质:

1.(只考虑新节点)根据以下的构造过程，kruskal重构树是一颗二叉树，并符合二叉堆的性质。

2.原树两点间的的最大边权就是kruskal重构树上两点的lca的权值。

3.重构树中代表原树中的点的节点全是叶子节点，其余节点都代表了一条边的边权。

根据这些美妙性质，kruskal重构树可以解决一些从A点走到B点的所有路径中，最长的边最小值是多少之类的傻逼问题

具体的实现:kruskal重构树就是在原本的kruskal算法中(先假设是求最小生成树)，每次查到两个不在同一集合的点，就新开一个节点，然后把两个节点的祖先节点分别向新节点连边，不计边权，但是要记录新点的点权，就是连接两个点的边的边权。

这样一来，新点的点权的含义就是左右子树中的点想要互通，必须要走至少一条边权等于这个点权的边。

也就是说，给定两个点，他们想要联通，所经过的所有路径中最短的边的最大值，就是两个点在kruskal重构树上的lca的点权。

虽说kruskal重构树是基于kruskal算法得到的最小生成树上使用，但也可推广到图中两点路径中最短边的最大值的求解。

不理解的话可以拿稿纸手推，肯定是构不出反例的

若一个点能通过一条路径到达，那么我们走最小生成树上的边也一定能到达该节点。

这句话应该是那类傻逼问题的核心了吧

NOIP2013货车运输

A国有n座城市，编号从1到n，城市之间有m条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有q辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

对于100%的数据0<n<10,000,0<m<50,000,0<q<30,000,0≤z≤100,0000<n<10,000,0<m<50,000,0<q<30,000,0≤z≤100,000。

转化问题：求两点之间所有路径中，最短的边的最大值。

Kruskal重构树模板题。每个询问实际上就是询问在最大生成树中的u,v之间的路径的最小边的权值。

构造重构树，边权按照从大到小的顺序排序，第一次使两个集合联通的边，一定是使这两个集合联通的最长的边，把边权当成重构树上的点权，就能转化成lca求解答案。

#include<bits/stdc++.h>//kruskal重构树,求两点之间所有的路径中，最短的边的最大值
using namespace std;
int n,m,q;
int nxt[200010],to[200010],head[50010],w[50010],tot;//重构树的边，w是新树点权
int cnt;
int f[50010];//kruskal算法的并查集
int fa[50010][20],dep[50010];//用于求lca
int vis[50010];
struct orz//用于kruskal算法
{
    int x,y,val;
}a[100010];
char buf[1<<15],*fs,*ft;
inline char getc(){return (ft==fs&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),ft==fs))?0:*fs++;}
inline int read()
{
    int x=0,f=1;  char ch=getc();
    while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getc();}
    while(isdigit(ch))  {x=(x<<1)+(x<<3)+(ch^48);  ch=getc();}
    return x*f;
}
void put(int x)
{
    if(x==0){putchar('0');putchar('\n');return;}
    if(x<0){putchar('-');x=-x;}
    int num=0;char ch[16];
    while(x) ch[++num]=x%10+'0',x/=10;
    while(num) putchar(ch[num--]);
    putchar('\n');
}
inline int my(orz a,orz b)
{
    return a.val>b.val;
}
inline int find(int x)
{
    int r=x,mid,j=x;
    while(r!=f[r]) r=f[r];
    while(j!=f[j]) mid=f[j],f[j]=r,j=mid;
    return r;
}
inline void add(int xx,int yy)
{
    to[++tot]=yy;nxt[tot]=head[xx];head[xx]=tot;
}
void dfs(int x)//预处理lca
{
    vis[x]=1;
    for(int ct=head[x];ct;ct=nxt[ct])
    {
        int y=to[ct];
        fa[y][0]=x;
        for(int i=1;i<=15;++i)
            fa[y][i]=fa[fa[y][i-1]][i-1];
        dep[y]=dep[x]+1;
        dfs(y);
    }
}
inline int lca(int x,int y)//求解lca
{
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=15;i>-1;--i) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
    if(x==y) return x;
    for(int i=15;i>-1;--i) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=m;++i)
        a[i].x=read(),a[i].y=read(),a[i].val=read();
    for(int i=1;i<=n;++i)f[i]=i,f[n+i]=n+i;//并查集初始化

    cnt=n;sort(a+1,a+m+1,my);//kruskal算法+重构
    for(int i=1;i<=m;++i)
    {
        int fx=find(a[i].x),fy=find(a[i].y);
        if(fx!=fy)
            f[fx]=f[fy]=++cnt,w[cnt]=a[i].val,add(cnt,fx),add(cnt,fy);
    }

    for(int i=cnt;i>n;--i)//预处理lca,注意原图可能不联通，所以我们可能构出了一个森林
        if(!vis[i])
            dep[i]=1,fa[i][0]=i,dfs(i);

    q=read();//处理询问
    for(int i=1;i<=q;++i) 
    {
        int xx=read(),yy=read();
        if(find(xx)!=find(yy)) put(-1);//两点可能不联通
        else put(w[lca(xx,yy)]);
    }
    return 0;
}

NOI2018归程

由于题面太长所以不复制了，请自行查找题面。

这道题其实挺好的，巧妙糅合了许多算法和技巧，但均不超过NOIP难度，是一道良好的NOI送分题。(但是spfa已经死了)

解这道题的前置知识：

1. dijkstra算法
2. kruskal重构树
3. 倍增思想
4. lca(树上倍增版)

掌握了这些算法知识，就可以着手解决这道题了。

首先，我们可以用dijkstra求出1到所有点的距离。

我们注意到有一个海拔的参数，这决定我们从出生点可以跑到哪些地方。

转化:求出从出生点能到哪些点以及这些点到1的最短距离。

这时候我们拿出kruskal重构树这个东西(实在不好想)

按照海拔从高到低重构，由kruskal重构树的二叉堆性质我们发现限制越低我们就能到达越远的地方。

所以我们考虑在新树的节点上存储两个值:海拔、距离。

海拔是指以这个点为根的子树能够互相到达，并且只经过大于等于这个海拔的路径。这时候每个新树节点表示以它为根的子树中的节点可以互相到达，且经过的最低海拔就是该点权值。

距离是指以这个点为子树的所有节点到1的距离的最小值。

这时候我们发现距离和海拔两个参数都符合二叉堆的性质，也就是有单调性，就可以用倍增的算法了。

我们对一个出生点v，求出深度最小的u，使得v在以u为根节点的子树中，并且u点的海拔>限制海拔。

这个点存储的距离就是答案。

因为既然倍增到了u点,就已经保证了u点的子树之间都可以无代价互相到达，这棵子树的叶子就是开车能到达的节点。这些节点到1的距离的最小值自然就是答案。(因为总没有其他方法，使得到1步行的距离比先开车再走最短路的距离短了吧，否则就是在扇dijsktra算法的脸啊）

其他的就是细节问题了，注意本题强制在线以及T组数据，顺便计算好要开多大的数组。(因为数组开小RE两次)

#include<bits/stdc++.h>
using namespace std;
int nxt[1200010],to[1200010],head[600010],val[1200010],tot;
int w[600010],f[600010],fa[600010][21],dis[1200010],vis[1200010],cnt;
struct orz1
{
    int x,y,l,a;
}a[400010];
int t,n,m,q,k,s;
int v,p,lastans;
char buf[1<<15],*ft,*fs;
inline char getc(){return (ft==fs&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),ft==fs))?0:*fs++;}
inline int read()
{
    int num=0;char ch=getc();
    while(!isdigit(ch))ch=getc();
    while(isdigit(ch))num=(num<<1)+(num<<3)+(ch^48),ch=getc();
    return num;
}
inline void put(int x)
{
    if(x==0) {putchar('0');putchar('\n');return ;}
    if(x<0) {putchar('-');x=-x;}
    int num=0;char ch[16];
    while(x) ch[++num]=x%10+'0',x/=10;
    while(num) putchar(ch[num--]);
    putchar('\n');
    return ;
}
priority_queue<pair<int,int> > qq;
inline int my(orz1 a,orz1 b){return a.a>b.a;}
inline void add(int xx,int yy,int vv)
{
    to[++tot]=yy,val[tot]=vv,nxt[tot]=head[xx],head[xx]=tot;
}
inline int find(int x)
{
    int r=x,j=x,mid;
    while(r!=f[r]) r=f[r];
    while(j!=f[j]) mid=f[j],f[j]=r,j=mid;
    return r;
}
inline void dijkstra(int st)
{
    memset(dis,127,sizeof(dis));
    dis[st]=0;
    qq.push(make_pair(0,st));
    while(!qq.empty())
    {
        int x=qq.top().second;
        qq.pop();vis[x]=1;
        for(int ct=head[x];ct;ct=nxt[ct])
        {
            int y=to[ct];
            if(dis[y]>dis[x]+val[ct])
            {
                dis[y]=dis[x]+val[ct];
                qq.push(make_pair(-dis[y],y));
            }
        }
    }
}
inline int minmy(int a,int b){return a>b?b:a;}
void dfs(int x)
{
    for(int ct=head[x];ct;ct=nxt[ct])
    {
        int y=to[ct];
        fa[y][0]=x;for(int i=1;i<=20;++i)fa[y][i]=fa[fa[y][i-1]][i-1];
        if(y>n)dfs(y);
        dis[x]=minmy(dis[x],dis[y]);
    }
}
inline int bei(int x)
{
    int u=x;
    for(int i=20;i>-1;--i) if(fa[u][i]&&w[fa[u][i]]>p) u=fa[u][i];
    return dis[u];
}
int main()
{
    t=read();
    while(t--)
    {
        memset(head,0,sizeof(head));
        memset(w,0,sizeof(w));
        memset(fa,0,sizeof(fa));
        memset(vis,0,sizeof(vis));tot=0;lastans=0;
        n=read(),m=read();
        for(register int i=1;i<=m;++i)
        {
            int xx=read(),yy=read(),vv=read(),aa=read();
            a[i].x=xx,a[i].y=yy,a[i].l=vv,a[i].a=aa;
            add(xx,yy,vv),add(yy,xx,vv);
        }
        dijkstra(1);
        sort(a+1,a+1+m,my);
        for(register int i=1;i<=n;++i) f[i]=i,f[n+i]=n+i;
        cnt=n;
        for(register int i=1;i<=m;++i) 
        {
            int fx=find(a[i].x),fy=find(a[i].y);
            if(fx!=fy)
            {
                f[fx]=f[fy]=++cnt;
                add(cnt,fx,0);add(cnt,fy,0);
                w[cnt]=a[i].a;
            }
        }
        dfs(cnt);
        q=read(),k=read(),s=read();
        for(register int i=1;i<=q;++i)
        {
            v=(read()+k*lastans-1)%n+1,p=(read()+k*lastans)%(s+1);
            lastans=bei(v);
            put(lastans);
        }
    }
    return 0;
}