[学习笔记]Kruskal重构树

考虑 $kruskal$ 算法

for(ri i=1;i<=m;i++) {
    int x=getfather(e[i].x),y=getfather(e[i].y);
    if(x!=y) {
        father[y]=x;
        ans+=e[i].x;
    }
}

我们这样做可以求出最小/大生成树
如果我们每次合并，都新建一个节点，再与 $x,y$ 连边，并用并查集合并，就是 $kruskal$ 重构树

void kruskal() {
    sort(e+1,e+m+1,cmp);
    for(ri i=1;i<=2*n-1;i++)father[i]=i;
    now=n;
    for(ri i=1;i<=m;i++) {
        int x=getfather(e[i].x),y=getfather(e[i].y);
        if(x!=y) {
            ++now;
            son[now][0]=x;
            son[now][1]=y;
            father[x]=now,father[y]=now;
            val[now]=e[i].z;
        }
    }
}

性质

$1$ 总点数 $2n-1$
很好证，边最多加 $n-1$ 条，原点有 $n$ 个，总 $2n-1$ 个

$2$ 二叉树易得

$3$ 所有 $1-n$ 的节点都是叶子易得

$4$ （最小生成树）原图上 $x,y$ 所有路径中，最大边权最小的那一条路径的边的最大值，就是 $val[lca(x,y)]$
最大生成树反之

$5$ $4$ 的扩展，即 $x$ 子树内叶节点可以通过所有 $>=$ 或 $<=$ $val[x]$ 的边互相到达

例题

$1$
$NOIP2013-D1T3$ 货车运输
https://www.luogu.com.cn/problem/P1967
问题描述 $A$ 国有 $n$ 座城市，编号从 $1$ 到 $n$ ，城市之间有 $m$ 条双向道路。
每一条道路对车辆都有重量限制，简称限重。
现在有 $q$ 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

$Solution$
考虑建最大生成树，显然货车走的边一定在最大生成树上
那么建出 $kruskal$ 重构树， $val[lca(x,y)]$ 即是答案

$Code$

#include <bits/stdc++.h>
#define ri register int
#define ll long long
using namespace std;
const int Maxn=1e5;
const int Maxm=5e5;
const int Lgn=20;
struct Edge {
    int x,y,z;
}e[Maxm+5];
int val[2*Maxn+5],father[2*Maxn+5],son[2*Maxn+5][2],n,m,q,now;
int dep[2*Maxn+5],st[2*Maxn+5][Lgn+5];
bool cmp(Edge a,Edge b) {
    return a.z>b.z;
}
int getfather(int v) {
    return father[v]==v?v:father[v]=getfather(father[v]);
}
void kruscal() {
    sort(e+1,e+m+1,cmp);
    for(ri i=1;i<=2*n-1;i++)father[i]=i;
    now=n;
    for(ri i=1;i<=m;i++) {
        int x=getfather(e[i].x),y=getfather(e[i].y);
        if(x!=y) {
            ++now;
            son[now][0]=x;
            son[now][1]=y;
            father[x]=now,father[y]=now;
            val[now]=e[i].z;
        }
    }
}
void dfs(int u,int fa) {
    dep[u]=dep[fa]+1;st[u][0]=fa;
    int t=ceil(log2(dep[u]));
    for(ri i=1;i<=t;i++)st[u][i]=st[st[u][i-1]][i-1];
    if(u>n) {
        dfs(son[u][0],u);
        dfs(son[u][1],u);
    }
}
int go_up(int u,int k) {
    int t=ceil(log2(dep[u]));
    for(ri i=0;i<=t;i++)
        if((k>>i)&1)u=st[u][i];
    return u;
}
int lca(int x,int y) {
    if(dep[x]<dep[y])swap(x,y);
    x=go_up(x,dep[x]-dep[y]);
    if(x==y)return x;
    int t=ceil(log2(dep[x]));
    for(ri i=t;i>=0;i--)
        if(st[x][i]!=st[y][i]) {
            x=st[x][i];
            y=st[y][i];
        }
    return st[x][0];
}
int main() {
    scanf("%d%d",&n,&m);
    for(ri i=1;i<=m;i++)scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);
    kruscal();
    dfs(now,0);
    scanf("%d",&q);
    while(q--) {
        int x,y;
        scanf("%d%d",&x,&y);
        if(getfather(x)!=getfather(y))printf("-1\n");
        else printf("%d\n",val[lca(x,y)]);
    }
    return 0;
}

$2$ 删边
https://ac.nowcoder.com/acm/contest/5205/E
问题描述
一个 $n$ 个节点 $m$ 条带权边的无向连通图。
有 $q$ 次询问，每次询问图中 $k_i$ 个互不相同的点，你可以选择一个数 $x$ ，然后将图中所有边权小于等于 $x$ 的边删除。求当删除这些边后 $k_i$ 个点互不连通时，求 $x$ 的最小值。
注意，本题强制在线

$Solution$
考虑建最大生成树
这里一定要想清楚，不要建错了生成树
我们不可能对于每个点枚举其他点，求 $val[lca(x,y)]$
所以分析一下性质
同一条链上， $dep[x]$ 越小， $val[x]$ 越小
所以，对我们的阈值 $x$ 的限制最强的，其实是最深的那些 $LCA$
那怎么找出最深的 $LCA$ ？
考虑按 $dfs$ 序排序
画一下图会发现最浅的 $LCA$ 一定在相邻两个点的 $LCA$ 之中
很好理解， $dfs$ 序记录被访问的时间，更大的 $LCA$ 如果在同一棵子树中，对答案无影响，如果不在，则会更浅
因为 $\sum k_i \leq 1 \times 10^6$ ，所以可过

$Code$

#include <bits/stdc++.h>
#define ri register int
#define ll long long
using namespace std;
const int Maxn=5e5;
const int Lgn=20;
struct Edge {
    int x,y,z;
}e[Maxn+5];
int father[2*Maxn+5];
int a[Maxn+5],n,m,q,vt,now;
int son[2*Maxn+5][2],val[2*Maxn+5],dfn[2*Maxn+5],st[2*Maxn+5][Lgn+5],dep[2*Maxn+5];
static char buf[30000000],*p1=buf,*p2=buf,obuf[30000000],*p3=obuf;
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
#define putchar(x) (p3-obuf<1000000)?(*p3++=x):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=x)
template<typename item>
inline void read(register item &x)
{
    x=0;register char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
static char cc[7000000];
template<typename item>
inline void print(register item x)
{ 
    ri len=0;
    do {cc[len++]=x%10+'0',x/=10;}while(x);
    while(len--)putchar(cc[len]);
}
bool cmp1(Edge a,Edge b) {
    return a.z>b.z;
}
bool cmp2(int a,int b) {
    return dfn[a]<dfn[b];
}
int getfather(int v) {
    return father[v]==v?v:father[v]=getfather(father[v]);
}
void kruscal() {
    sort(e+1,e+m+1,cmp1);
    for(ri i=1;i<=2*n-1;i++)father[i]=i;
    now=n;
    for(ri i=1;i<=m;i++) {
        int x=getfather(e[i].x),y=getfather(e[i].y);
        if(x!=y) {
            ++now;
            son[now][0]=x;
            son[now][1]=y;
            father[x]=now,father[y]=now;
            val[now]=e[i].z;
        }
    }
}
void dfs(int u,int fa) {
    dep[u]=dep[fa]+1;st[u][0]=fa;dfn[u]=++vt;
    int t=ceil(log2(dep[u]));
    for(ri i=1;i<=t;i++)st[u][i]=st[st[u][i-1]][i-1];
    if(u>n) {
        dfs(son[u][0],u);
        dfs(son[u][1],u);
    }
}
int go_up(int u,int k) {
    int t=ceil(log2(dep[u]));
    for(ri i=0;i<=t;i++)
        if((k>>i)&1)u=st[u][i];
    return u;
}
int lca(int x,int y) {
    if(dep[x]<dep[y])swap(x,y);
    x=go_up(x,dep[x]-dep[y]);
    if(x==y)return x;
    int t=ceil(log2(dep[x]));
    for(ri i=t;i>=0;i--)
        if(st[x][i]!=st[y][i]) {
            x=st[x][i];
            y=st[y][i];
        }
    return st[x][0];
}
int main() {
    read(n),read(m),read(q);
    for(ri i=1;i<=m;i++)read(e[i].x),read(e[i].y),read(e[i].z);
    kruscal();
    dfs(now,0);
    int ans=0;
    while(q--) {
        int k;
        read(k);
        for(ri i=1;i<=k;i++)read(a[i]),a[i]^=ans;
        sort(a+1,a+k+1,cmp2);
        ans=0;
        for(ri i=2;i<=k;i++)ans=max(ans,val[lca(a[i],a[i-1])]);
        print(ans),putchar('\n');
    }
    fwrite(obuf,p3-obuf,1,stdout);
    return 0;
}

$3$ $NOI2018归程$
问题描述
本题的故事发生在魔力之都，在这里我们将为你介绍一些必要的设定。

魔力之都可以抽象成一个 $n$ 个节点、 $m$ 条边的无向连通图（节点的编号从 $1$ 至 $n$ ）。我们依次用 $l,a$ 描述一条边的长度、海拔。

作为季风气候的代表城市，魔力之都时常有雨水相伴，因此道路积水总是不可避免的。由于整个城市的排水系统连通，因此有积水的边一定是海拔相对最低的一些边。

我们用水位线来描述降雨的程度，它的意义是：所有海拔不超过水位线的边都是有积水的。

$Yazid$ 是一名来自魔力之都的 $OIer$ ，刚参加完 $ION2018$ 的他将踏上归程，回到他温暖的家。

$Yazid$ 的家恰好在魔力之都的 $1$ 号节点。对于接下来 $Q$ 天，每一天 $Yazid$ 都会告诉你他的出发点，以及当天的水位线。

每一天， $Yazid$ 在出发点都拥有一辆车。这辆车由于一些故障不能经过有积水的边。

$Yazid$ 可以在任意节点下车，这样接下来他就可以步行经过有积水的边。但车会被留在他下车的节点并不会再被使用。

需要特殊说明的是，第二天车会被重置，这意味着：
车会在新的出发点被准备好。 $Yazid$ 不能利用之前在某处停放的车。 $Yazid$ 非常讨厌在雨天步行，因此他希望在完成回家这一目标的同时，最小化他步行经过的边的总长度。请你帮助 $Yazid$ 进行计算。
强制在线

$Solution$
~~SPFA死了~~
考虑坐车可以走到哪些点
我们就是 $x$ 求经过海拔大于 $p$ 的点
性质 $5$ 就是干这事的
建最大重构树，以 $a$ 为边权
我们向上倍增，找到最浅的、海拔大于 $p$ 的点
这个点子树内所有叶节点就是 $x$ 坐车可以到达的节点
那我们把这些点到 $1$ 的最短路取 $min$ 即可
这个可以预处理

$Code$

#include <bits/stdc++.h>
#define ri register int
#define ll long long
using namespace std;
const int Maxn=2e5;
const int Maxm=4e5;
const int Lgn=20;
const int Inf=2e9+1;
struct Edge {
    int x,y,z;
}e[Maxm+5];
struct Path {
    int u,dis;
};
priority_queue<Path>q;
int lt[Maxn+5],nt[2*Maxm+5],ed[2*Maxm+5],val[2*Maxm+5];
int n,m,cnt,Q,K,S,now,T;
int father[2*Maxn+5],son[2*Maxn+5][2],mindis[2*Maxn+5],dep[2*Maxn+5],st[2*Maxn+5][Lgn+5],v[2*Maxn+5];
int dis[Maxn+5],mark[Maxn+5];
static char buf[30000000],*p1=buf,*p2=buf,obuf[30000000],*p3=obuf;
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
#define putchar(x) (p3-obuf<1000000)?(*p3++=x):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=x)
template<typename item>
inline void read(register item &x)
{
    x=0;register char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
static char cc[7000000];
template<typename item>
inline void print(register item x)
{ 
    ri len=0;
    do {cc[len++]=x%10+'0',x/=10;}while(x);
    while(len--)putchar(cc[len]);
}
bool cmp(Edge a,Edge b) {
    return a.z>b.z;
}
bool operator<(Path a,Path b) {
    return a.dis>b.dis;
}
int getfather(int v) {
    return father[v]==v?v:father[v]=getfather(father[v]);
}
void addedge(int x,int y,int z) {
    ed[++cnt]=y;nt[cnt]=lt[x];lt[x]=cnt;
    val[cnt]=z;
}
void kruscal() {
    sort(e+1,e+m+1,cmp);
    for(ri i=1;i<=2*n-1;i++)father[i]=i;
    now=n;
    for(ri i=1;i<=m;i++) {
        int x=getfather(e[i].x),y=getfather(e[i].y);
        if(x!=y) {
            ++now;
            son[now][0]=x;
            son[now][1]=y;
            father[x]=now,father[y]=now;
            v[now]=e[i].z;
        }
    }
}
void init() {
    for(ri i=1;i<=n;i++)dis[i]=Inf,mark[i]=0;
    dis[1]=0;
    q.push((Path){1,0});
}
void dij() {
    while(!q.empty()) {
        Path t=q.top();q.pop();
        int u=t.u;
        if(mark[u])continue;
        mark[u]=1;
        for(ri i=lt[u];i;i=nt[i]) {
            int v=ed[i],l=val[i];
            if(dis[v]>dis[u]+l) {
                dis[v]=dis[u]+l;
                q.push((Path){v,dis[v]});
            }
        }
    }
}
void dfs(int u,int fa) {
    dep[u]=dep[fa]+1;st[u][0]=fa;
    int t=ceil(log2(dep[u]));
    for(ri i=1;i<=t;i++)st[u][i]=st[st[u][i-1]][i-1];
    if(u>n) {
        int x=son[u][0],y=son[u][1];
        dfs(x,u),dfs(y,u);
        mindis[u]=min(mindis[x],mindis[y]);
    }
    else mindis[u]=dis[u];
}
int main() {
    read(T);
    while(T--) {
        read(n),read(m);
        memset(lt,0,sizeof(lt));cnt=0;
        for(ri i=1;i<=m;i++) {
            int x,y,l,a;
            read(x),read(y),read(l),read(a);
            e[i].x=x,e[i].y=y,e[i].z=a;
            addedge(x,y,l);
            addedge(y,x,l);
        }
        kruscal();
        init();
        dij();
        dfs(now,0);
        read(Q),read(K),read(S);
        int ans=0;
        while(Q--) {
            int u,p;
            read(u),read(p);
            u=(u+K*ans-1)%n+1;
            p=(p+K*ans)%(S+1);
            int t=ceil(log2(dep[u]));
            for(ri i=t;i>=0;i--)
                if(v[st[u][i]]>p)u=st[u][i];
            print(ans=mindis[u]);
            putchar('\n');
        }
    }
    fwrite(obuf,p3-obuf,1,stdout);
    return 0;
}

$4$ $IOI2018$ 狼人
在日本的茨城县内共有 $N$ 个城市和 $M$ 条道路。这些城市是根据人口数量的升序排列的，依次编号为 $0$ 到 $N-1$ 。每条道路连接两个不同的城市，并且可以双向通行。由这些道路，你能从任意一个城市到另外任意一个城市。

你计划了 $Q$ 个行程，这些行程分别编号为 $0$ 至 $Q-1$ 。第 $i$ ( $0 \leq i \leq Q-1$ )个行程是从城市 $S_i$ 到城市 $E_i$ 。

你是一个狼人。你有两种形态：人形和狼形。在每个行程开始的时候，你是人形。在每个行程结束的时候，你必须是狼形。在行程中，你必须要变身（从人形变成狼形）恰好一次，而且只能在某个城市内（包括可能是在 $S_i$ 或 $E_i$ 内）变身。

狼人的生活并不容易。当你是人形时，你必须避开人少的城市，而当你是狼形时，你必须避开人多的城市。对于每一次行程 $i$ ( $0 \leq i \leq Q-1$ )，都有两个阈值 $R_i$ 和 $L_i$ ( $0 \leq L_i \leq R_i \leq N-1$ )，用以表示哪些城市必须要避开。准确地说，当你是人形时，你必须避开城市 $0,1,...,L_i-1$ ；而当你是狼形时，则必须避开城市 $R_i+1,R_i+2,...,N-1$ 。这就是说，在行程 $i$ 中你必须在城市 $L_i,L_i+1,...,R_i$ 中的其中一个城市内变身。

你的任务是，对每一次行程，判定是否有可能在满足上述限制的前提下，由城市 $S_i$ 走到城市 $E_i$ 。你的路线可以有任意长度。

$Solution$
考虑出处理所有能以人形到达的城市，和狼形能到达的城市
对于人形，我们将边 $(u,v)$ 的权设为 $min(u,v)$
这样，我们建最大重构树，向上倍增到最浅的边权大于等于 $L$ 的点，子树内的叶子就是可以到的城市
狼性边权改为 $max(u,v)$ ，做最小生成树，同样倍增
那么我们要看这两个城市集合有没有交集
显然维护集合是不行的，那么考虑一个城市有没有出现在这两个集合里面
注意到若城市 $x$ 在两个集合里，则一定在倍增到的点的子树里
也就是说，设 $in[i][0/1]$ 为点 $i$ 第一/二棵里的 $DFS$ 序，设 $x,y$ 为倍增到的点
城市 $u$ 满足

$in[x][0] \leq in[u][0] \leq out[x][0]$
$in[y][1] \leq in[u][1] \leq out[y][1]$
典型的二位偏序
那么有两种方法
一种是离线+树状数组
第二种是主席树，以第一棵的 $DFS$ 序为版本，第二棵的 $DFS$ 序为区间
将一个路线看做一个询问，问在这个范围内的点有没有，有就是可行的

$Code$

#include <bits/stdc++.h>
#define ri register int
#define ll long long
using namespace std;
const int Maxn=2e5;
const int Maxm=4e5;
const int Lgn=20;
struct Edge {
    int x,y,z;
}e[Maxm+5];
struct Query {
    int x,y,id,k;
}q[Maxn*4+5];
struct Point {
    int x,y;
}p[Maxn+5];
int ans[Maxn+5],c[2*Maxn+5],n,m,Q,vt,tot;
int father[2*Maxn+5];
int val[2][2*Maxn+5],son[2][2*Maxn+5][2],st[2][2*Maxn+5][Lgn+5],dep[2][2*Maxn+5],in[2][2*Maxn+5],out[2][2*Maxn+5];
bool cmp1(Edge a,Edge b) {
    return a.z>b.z;
}
bool cmp2(Edge a,Edge b) {
    return a.z<b.z;
}
bool cmp3(Query a,Query b) {
    return a.x<b.x;
}
bool cmp4(Point a,Point b) {
    return a.x<b.x;
}
int lowbit(int x) {return x&(-x);}
void add(int x,int d) {for(;x<=2*n-1;x+=lowbit(x))c[x]+=d;}
int getsum(int x) {int ret=0;for(;x>=1;x-=lowbit(x))ret+=c[x];return ret;}
int getfather(int v) {
    return father[v]==v?v:father[v]=getfather(father[v]);
}
void dfs(int u,int k,int fa) {
    in[k][u]=++vt;
    dep[k][u]=dep[k][fa]+1;st[k][u][0]=fa;
    int s=ceil(log2(dep[k][u]));
    for(ri i=1;i<=s;i++)st[k][u][i]=st[k][st[k][u][i-1]][i-1];
    if(u>n) {
        int x=son[k][u][0],y=son[k][u][1];
        dfs(x,k,u),dfs(y,k,u);
    }
    out[k][u]=vt;
}
void kruscal() {
    for(ri i=1;i<=m;i++)e[i].z=min(e[i].x,e[i].y);
    sort(e+1,e+m+1,cmp1);
    for(ri i=1;i<=n;i++)father[i]=i;
    int now=n;
    for(ri i=1;i<=m;i++) {
        int x=getfather(e[i].x),y=getfather(e[i].y);
        if(x!=y) {
            ++now;father[now]=now;
            son[0][now][0]=x;
            son[0][now][1]=y;
            father[x]=now,father[y]=now;
            val[0][now]=e[i].z;
        }
    }
    dfs(now,0,0);
    for(ri i=1;i<=m;i++)e[i].z=max(e[i].x,e[i].y);
    sort(e+1,e+m+1,cmp2);
    for(ri i=1;i<=n;i++)father[i]=i;
    now=n;
    for(ri i=1;i<=m;i++) {
        int x=getfather(e[i].x),y=getfather(e[i].y);
        if(x!=y) {
            ++now;father[now]=now;
            son[1][now][0]=x;
            son[1][now][1]=y;
            father[x]=now,father[y]=now;
            val[1][now]=e[i].z;
        }
    }
    vt=0;
    dfs(now,1,0);
}
void make_query(int u,int v,int id) {
    int x1=in[0][u],y1=in[1][v],x2=out[0][u],y2=out[1][v];
    q[++tot]=(Query){x1-1,y1-1,id,1};
    q[++tot]=(Query){x2,y1-1,id,-1};
    q[++tot]=(Query){x1-1,y2,id,-1};
    q[++tot]=(Query){x2,y2,id,1};
}
int main() {
    scanf("%d%d%d",&n,&m,&Q);
    for(ri i=1;i<=m;i++) {
        scanf("%d%d",&e[i].x,&e[i].y);
        ++e[i].x,++e[i].y;
    }
    kruscal();
    val[1][0]=n+1;
    for(ri i=1;i<=Q;i++) {
        int x,y,l,r;
        scanf("%d%d%d%d",&x,&y,&l,&r);
        ++x,++y,++l,++r;
        int s=ceil(log2(dep[0][x]));
        for(ri j=s;j>=0;j--)
            if(val[0][st[0][x][j]]>=l)x=st[0][x][j];
        s=ceil(log2(dep[1][y]));
        for(ri j=s;j>=0;j--)
            if(val[1][st[1][y][j]]<=r)y=st[1][y][j];
        make_query(x,y,i);
    }
    for(ri i=1;i<=n;i++)p[i].x=in[0][i],p[i].y=in[1][i];
    sort(q+1,q+tot+1,cmp3);
    sort(p+1,p+n+1,cmp4);
    int now=1;
    for(ri i=1;i<=tot;i++) {
        while(p[now].x<=q[i].x&&now<=n)add(p[now].y,1),++now;
        ans[q[i].id]+=getsum(q[i].y)*q[i].k;
    }
    for(ri i=1;i<=Q;i++)printf("%d\n",ans[i]?1:0);
    return 0;
}