Kruskal重构树

Kruskal重构树

考虑这样一个问题：给定一个 $n$ 个点 $m$ 条边的带权无向图。多次询问 $u$ 到 $v$ 的路径中，边权的最小值最大的路径。

我们仿照Kruskal算法，将边权从大到小排序，依次加入。如果两端点已经连通，那么这条边没有意义（因为它的权值更小）。最终，至多只有 $n-1$ 条边有意义，得到了一棵生成树或生成森林。

Kruskal重构树利用点权信息表示边权信息。具体地，在上述算法进行合并的过程中，每当合并两个点时，便通过一个点权为该边边权的点将两点进行合并。**（因此，并查集相关需要开两倍大小，包括初始化）**这样，当询问时，两点最近公共祖先的权值就是答案。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=5e4+5;
struct edge
{
    int u,v,w;
    bool operator < (const edge &x) const {return w>x.w;}
}e[N];
int f[2*N];
int find(int x) {return f[x]==x?x:f[x]=find(f[x]);}
int cnt,val[2*N];
int d[2*N],pa[2*N][25];
int get_depth(int u)
{
    if(d[u]) return d[u];
    if(pa[u][0]==0) return d[u]=0;
    return d[u]=get_depth(pa[u][0])+1;
}
int lca(int u,int v)
{
    if(d[u]<d[v]) swap(u,v);
    for(int i=19;i>=0;i--)
        if(d[pa[u][i]]>=d[v]) u=pa[u][i];
    if(u==v) return u;
    for(int i=19;i>=0;i--)
        if(pa[u][i]!=pa[v][i])
        {
            u=pa[u][i];
            v=pa[v][i];
        }
    return pa[u][0];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w;
    sort(e+1,e+m+1);
    cnt=n;
    for(int i=1;i<=n;i++) val[i]=0;
    for(int i=1;i<=2*n;i++) d[i]=0,f[i]=i;
    for(int i=1;i<=m;i++)
    {
        int u=find(e[i].u),v=find(e[i].v);
        if(u==v) continue;
        f[u]=f[v]=++cnt;
        val[cnt]=e[i].w;
        pa[u][0]=pa[v][0]=cnt;
    }
    for(int i=1;i<20;i++)
        for(int j=1;j<=2*n;j++) pa[j][i]=pa[pa[j][i-1]][i-1];
    for(int i=1;i<=2*n;i++) get_depth(i);
    int q;cin>>q;
    while(q--)
    {
        int x,y;cin>>x>>y;
        if(find(x)!=find(y)) 
        {
            cout<<-1<<'\n';
            continue;
        }
        cout<<val[lca(x,y)]<<'\n';
    }
    return 0;
}

练习

Gym103446H Life is a Game

题意

给出一张 $n$ 个点 $m$ 条边的连通图，每个点有点权，每条边有边权。$q$ 次询问，每次询问给出初始点和初始能力值，每到一个点可以获得该点点权的能力值，走每条边要求能力值不小于该边边权。求最终能获得的最大能力值。

数据范围：$1\leq n,m,q\leq 10^5$。

题解

将边从小到大排序建立重构树，由于图连通，所以得到的一定是一棵树。除了叶子结点以外，每个点都有点权，代表走过这条边所需要的最小能力值。而根据重构树的建树过程，每个点的点权都不超过它的父亲。所以，一旦一个点可以走到，那么该点子树内的所有点的能力值都能被获得。可以利用倍增维护向上走 $2^i$ 步需要的最小能力值：cost[j][i]=max(cost[j][i-1],cost[pa[j][i-1]][i-1])。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int a[2*maxn];
struct edge
{
    int u,v,w;
    bool operator < (const edge &x) const {return w<x.w;}
}e[maxn];
int f[2*maxn];
int find(int x) {return f[x]==x?x:f[x]=find(f[x]);}
int d[2*maxn],val[2*maxn],pa[2*maxn][20],cost[2*maxn][20];
vector<int> g[2*maxn];
ll siz[2*maxn];
void dfs(int u)
{
    siz[u]=a[u];
    for(auto v:g[u])
    {
        dfs(v);
        siz[u]+=siz[v];
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,q;cin>>n>>m>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w;
    sort(e+1,e+m+1);
    int cnt=n;
    for(int i=1;i<=2*n;i++) f[i]=i;
    for(int i=1;i<=m;i++)
    {
        int u=find(e[i].u),v=find(e[i].v);
        if(u==v) continue;
        f[u]=f[v]=++cnt;
        pa[u][0]=pa[v][0]=cnt;
        val[cnt]=e[i].w;
        g[cnt].push_back(u),g[cnt].push_back(v);
    }
    dfs(cnt);
    for(int i=1;i<=cnt;i++) cost[i][0]=val[pa[i][0]]-siz[i];
    for(int i=1;i<20;i++)
        for(int j=0;j<=cnt;j++)
        {
            pa[j][i]=pa[pa[j][i-1]][i-1];
            cost[j][i]=max(cost[j][i-1],cost[pa[j][i-1]][i-1]);
        }
    while(q--)
    {
        int x,k;cin>>x>>k;
        for(int i=19;i>=0;i--)
        {
            if(pa[x][i]!=0&&cost[x][i]<=k) x=pa[x][i];
        }
        cout<<k+siz[x]<<'\n';
    }
    return 0;
}