Kruskal 重构树
[您有新的未分配科技点][BZOJ3545&BZOJ3551]克鲁斯卡尔重构树
kruskal是一个性质优秀的算法
加入的边是越来越劣的
科学家们借这个特点尝试搞一点事情。
kruskal求最小生成树的过程，如果把加入的一个边新建一个节点的话，并且把k1,k2的father设为新点的话，会得到一个2*n大小的树
实际上已经非常明白地表示kruskal这个过程了。这个树叫kruskal重构树
每个点的权值定义为所代表的边的权值。叶子节点权值最优。
由于贪心，所以树上所有点，从儿子到祖先权值单调不优。（这是最关键的性质）
树的结构我们非常熟悉
所以各种算法纷至沓来。
具体怎么用？
BZOJ3545 Peaks：
在Bytemountains有N座山峰，每座山峰有他的高度h_i。有些山峰之间有双向道路相连，共M条路径，每条路径有一个困难值，这个值越大表示越难走。
现在有Q组询问，每组询问询问从点v开始只经过困难值小于等于x的路径所能到达的山峰中第k高的山峰，如果无解输出-1。N<=1e5,M,Q<=5*1e5
（不强制在线的话，直接离线排序+线段树合并或者启发式合并。（类似“永无乡”））
强制在线呢？
kruskal重构树登场！
对于只走小于x的边，会得到一个可以到达的联通块。
最小生成树的边上走，保证这个联通块是极大的。
联通块高度的第k大就是答案。
发现这个联通块对应重构树的一个子树！
重构树上，从v开始往上倍增找到最后一个权值小于等于x的点p
p对应的子树的叶子就是所有的联通块的点。（有点类似SAM的fail树？)
所以区间第k大，用dfs序处理一下，+主席树维护即可。
NOI2018归程
如果想到kruskal重构树（感觉学了应该都能想到，毕竟适用面也不是很广），那么这题就水了。
所能开车到达的集合里选择距离家最近的点下车。
kruskal重构树建出来（最大生成树），叶子赋予一个dis到1的距离。
dis用dij跑（因为出题人卡spfa）
然后dfs重构树处理信息，然后倍增处理询问。大功告成！
代码：
（很丑陋，见缝插针，而且mi、dep数组其实根本不需要）
#include<bits/stdc++.h>
#define reg register int
#define il inline
#define numb (ch^'0')
using namespace std;
typedef long long ll;
il void rd(int &x){
char ch;x=;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*+numb);
(fl==true)&&(x=-x);
}
namespace Miracle{
const int N=+;
const int M=+;
const ll inf=0x3f3f3f3f3f3f3f3f;
ll dis[N];
ll ans[*N];
int val[*N];
int n,m;
struct node{
int nxt,to;
int val;
}e[*N];
int hd[*N],cnt;
void add(int x,int y,int z){
e[++cnt].nxt=hd[x];
e[cnt].to=y;
e[cnt].val=z;
hd[x]=cnt;
}
int tot;
namespace dij{ bool vis[N];
struct po{
int x,d;
po(int xx,int dd){
x=xx;d=dd;
}
bool friend operator <(po a,po b){
return a.d>b.d;
}
};
priority_queue<po>q;
void dij(){
memset(vis,,sizeof vis);
memset(dis,0x3f,sizeof dis);
while(!q.empty()) q.pop();
dis[]=;
q.push(po(,));
while(!q.empty()){
po now=q.top();q.pop();
if(vis[now.x]) continue;
vis[now.x]=;
dis[now.x]=now.d;
for(reg i=hd[now.x];i;i=e[i].nxt){
int y=e[i].to;
if(vis[y]) continue;
q.push(po(y,dis[now.x]+e[i].val));
}
}
for(reg i=;i<=n;++i){
ans[i]=dis[i];
//mi[i][0]=0x3f3f3f3f;
}
}
} struct edge{
int x,y;
int l,a;
bool friend operator <(edge a,edge b){
return a.a>b.a;
}
}b[M];
//represent the value of edge
namespace kruscal{
int fa[*N];
int fin(int x){
return fa[x]==x?x:fa[x]=fin(fa[x]);
}
void main(){
for(reg i=;i<=n;++i) {
fa[i]=i;val[i]=0x3f3f3f3f;
}
tot=n;
// cout<<" tot "<<tot<<endl;
sort(b+,b+m+);
for(reg i=;i<=m;++i){
int k1=fin(b[i].x),k2=fin(b[i].y);
// cout<<" bb "<<tot<<" "<<i<<" : "<<b[i].x<<" "<<b[i].y<<" rt "<<k1<<" sand "<<k2<<endl;
if(k1!=k2){ ++tot;
fa[tot]=tot;
ans[tot]=inf; add(tot,k1,);
add(tot,k2,);
fa[k1]=fa[k2]=tot;
val[tot]=b[i].a;
}
}
} }
int fa[*N][];
int mi[*N][];
int dep[*N]; void dfs(int x,int d){
dep[x]=d;
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
fa[y][]=x;
mi[y][]=min(val[y],val[x]);
dfs(y,d+);
ans[x]=min(ans[x],ans[y]);
}
}
ll query(int x,int p){
for(reg j=;j>=;--j){
if(fa[x][j]){
if(mi[x][j]>p) x=fa[x][j];
}
}
return ans[x];
}
void clear(){
memset(fa,,sizeof fa);
memset(mi,0x3f,sizeof mi);
memset(dep,,sizeof dep);
memset(hd,,sizeof hd);
cnt=;
}
int main(){
int T;
rd(T);
while(T--){
rd(n);rd(m);
clear();
for(reg i=;i<=m;++i){
rd(b[i].x);rd(b[i].y);rd(b[i].l);rd(b[i].a);
add(b[i].x,b[i].y,b[i].l);
add(b[i].y,b[i].x,b[i].l);
}
dij::dij();
// cout<<" after dij "<<endl; memset(hd,,sizeof hd);
cnt=;
kruscal::main();
// cout<<" after kruc "<<endl; dfs(tot,);
// cout<<" after dfs "<<endl;
for(reg j=;j<=;++j){
for(reg i=;i<=tot;++i){
fa[i][j]=fa[fa[i][j-]][j-];
mi[i][j]=min(mi[i][j-],mi[fa[i][j-]][j-]);
}
} // cout<<" tot "<<tot<<endl;
// for(reg i=1;i<=tot;++i){
// cout<<" ii "<<i<<" val "<<val[i]<<" ans "<<ans[i]<<" fafa "<<fa[i][0]<<endl;
// }
int q,k,s;
rd(q);rd(k);rd(s);
ll las=;
int v,p;
while(q--){
rd(v);rd(p);
v=(v+k*las-)%n+;
p=(p+k*las)%(s+);
printf("%lld\n",las=query(v,p));
}
}
return ;
} }
signed main(){
Miracle::main();
return ;
} /*
Author: *Miracle*
Date: 2019/1/8 18:49:37
*/
这个算法适用面：
在线处理询问在经过小于（大于）某个边权的边所能到的集合里的信息。
主要性质是祖先权值的单调不优。
这个算法是对kruskal求最小生成树的操作过程的树形结构化，从而精确剖析过程，使得维护方便。
有异曲同工之妙的是动态点分治的分治树，也是对操作过程的树形结构化。
还有一个例题：（NOI和IOI都考了诶热度真高）
[IOI2018] werewolf 狼人
upda：2019.2.13
并查集重构树
除了Kruskal重构树之外，还有一个东西叫做并查集重构树
引入例题
n个点，q次操作，每次加入一条边（不会重边自环），或者查询两个点最早什么时候连通
n,q<=1e5
（某次jzoj考试题）
还是考虑具体维护出操作的结构
用按秩合并并查集，边权就是这次加入的边的时间值
发现，两个点第一次连通，一定是两个点并查集上路径最大值！
由于按秩合并，树高logn，可以暴力查询
如果是最后询问，可以建倍增数组，loglogn复杂度
对于一般的图，边权sort，然后按照上述做即可
毒瘤一些：
1.sort用松式基排
2.并查集按秩合并+路径压缩，另外开一个邻接表记录树
接近O(n)
性质：
1.越靠上权值越劣
2.两点间最大权值就是连通时间
比较优劣
并查集重构树：
劣势：子树不是一个区间（因为没有附加点）
优势：空间小，好写好调，两点间信息可以O(loglogn)快速求出。
kruskal重构树：
反过来。
劣势：难写一些，容易写错。
优势：多了附加点，经过小于vi的边到达的区域是子树，加上dfn序列很好维护。