前言

沟槽的南昌 J 题，永远的痛……

一、原理

在 kruskal 重构树里，图上的所有节点在重构树上都是叶子节点，即并查集中自己是一个集合。之后在跑 kruskal 建立最小生成树时，从边权较小的边开始考虑，每次将选择的边当作树上的节点。

构建的过程就是，当加入这条边可以使得 u 和 v 连通时，此时新建立一个节点连接 u 和 v 所在连通块的头节点，然后让这个新节点的点权为这条边的边权。在上图中，首先考察 2 和 4 之间边权为 1 的边，那么就建立 6 号点连接 2 和 4，点权为 1。之后考察到 1 和 3 边权为 2 的边，建立 7 号点。接着是连接 3 和 5 边权为 3 的边，此时就建立 8 号节点连接 7 号点和 5 号点。之后边权为 4 的边由于 1 和 5 已经连通，所以放弃。之后考察到 1 和 2 之间边权为 5 的边，就建立 9 号节点连接 6 号和 8 号节点，点权为 5，过程结束。

此时，如果要查想让 u 和 v 连通的最大边权的最小值，即瓶颈，这个答案就是 u 和 v 的 lca。这个是因为最小生成树同时就是最小瓶颈树，在重构的过程中，若某条边加入了树中，那么这条边必然就是连接两个连通块权值最小的边。此时，从重构树的叶子节点出发，越往上边权越大，所获得的连通性越好。

可以发现，Kruskal 重构树适用于解决在边权受限的情况下的图上问题。这是因为其可以通过倍增表往上跳，找到第一个不符合限制的边，而这个是存在单调性的！！此时其能到达的连通区域，就是这条边对应的节点 x 的一个子树。而对于子树，解决的方法就很多了。

二、题目

1.星际导航

#include <bits/stdc++.h>
using namespace std;

/*   /\_/\
*   (= ._.)
*   / >  \>
*/

/*
*想好再写
*注意审题 注意特判
*不要红温 不要急躁 耐心一点
*WA了不要立马觉得是思路不对 先耐心找反例
*/

#define endl '\n'
#define dbg(x) cout<<#x<<endl;cout<<x<<endl;
#define vdbg(a) cout<<#a<<endl;for(auto x:a)cout<<x<<" ";cout<<endl;
#define YES cout<<"YES"<<endl;return ;
#define Yes cout<<"Yes"<<endl;return ;
#define NO cout<<"NO"<<endl;return ;
#define No cout<<"No"<<endl;return ;
#define popcount __builtin_popcount
using ll=long long;
using i128=__int128;
using ld=long double;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
const int INF=1e9;
const ll INFLL=1e18;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
const int ddx[]={-2,-1,1,2,2,1,-1,-2};
const int ddy[]={1,2,2,1,-1,-2,-2,-1};

struct DSU{
    vector<int>father;
    //自定义

    DSU(int n){
        father.assign(n,0);
        for(int i=0;i<n;i++){
            father[i]=i;

        }
    }

    int find(int i){
        if(i!=father[i]){
            father[i]=find(father[i]);
        }
        return father[i];
    }

    bool same(int x,int y){
        return find(x)==find(y);
    }

    bool merge(int x,int y){
        int fx=find(x);
        int fy=find(y);
        if(fx==fy){
            return false;
        }

        father[fx]=fy;
        
        return true;
    }
};

void solve()
{
    int n,m;
    cin>>n>>m;
    vector<array<int,3>>edge(m+1);
    for(int i=1;i<=m;i++)
    {
        cin>>edge[i][0]>>edge[i][1]>>edge[i][2];
    }    

    DSU dsu(2*n+1);
    
    sort(edge.begin()+1,edge.end(),[&](auto &x,auto &y)
    {
        return x[2]<y[2];
    });

    int cnt=n;
    vector<vector<int>>g(2*n+1);
    vector<ll>a(2*n+1);

    for(int i=1;i<=m;i++)
    {
        auto [u,v,w]=edge[i];

        int fx=dsu.find(u);
        int fy=dsu.find(v);
        if(fx!=fy)
        {
            dsu.father[fx]=dsu.father[fy]=++cnt;
            dsu.father[cnt]=cnt;
            a[cnt]=w;
            
            g[cnt].push_back(fx);
            g[fx].push_back(cnt);
            g[cnt].push_back(fy);
            g[fy].push_back(cnt);
        }
    }

    const int MAXP=20;
    vector<int>dep(2*n+1);
    vector<vector<int>>stjump(2*n+1,vector<int>(MAXP+1));

    auto dfs=[&](auto &&self,int u,int fa)->void
    {
        dep[u]=dep[fa]+1;
        stjump[u][0]=fa;

        for(int p=1;p<=MAXP;p++){
            stjump[u][p]=stjump[stjump[u][p-1]][p-1];
        }
    
        for(auto v:g[u]){
            if(v!=fa){
                self(self,v,u);
            }
        }
    };

    auto query=[&](int a,int b)->int
    {
        if(dep[a]<dep[b]){
            swap(a,b);
        }
    
        for(int p=MAXP;p>=0;p--){
            if(dep[stjump[a][p]]>=dep[b]){
                a=stjump[a][p];
            }
        }
    
        if(a==b){
            return a;
        }
    
        for(int p=MAXP;p>=0;p--){
            if(stjump[a][p]!=stjump[b][p]){
                a=stjump[a][p];
                b=stjump[b][p];
            }
        }

        return stjump[a][0];
    };

    for(int i=1;i<=cnt;i++)
    {
        if(i==dsu.father[i])
        {
            dfs(dfs,i,0);
        }
    }

    int q;
    cin>>q;
    int x,y;
    while(q--)
    {
        cin>>x>>y;
        if(dsu.same(x,y))
        {
            int lca=query(x,y);
            cout<<a[lca]<<endl;
        }
        else
        {
            cout<<"impossible"<<endl;
        }
    }
}

void init()
{
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    init();
    while(t--)
    {
        solve();    
    }
    return 0;
}

完全板子题，实现时记得并查集和 st 表的大小都要开两倍。在建立好重构树后，为了处理多个连通块的情况，要分别从每个连通块的头出发 dfs 一遍，查询时也要判断是否在同一个连通块内。

2.youyou 的军训

这个题就体现出 kruskal 重构树的精髓了。

#include <bits/stdc++.h>
using namespace std;

/*   /\_/\
*   (= ._.)
*   / >  \>
*/

/*
*想好再写
*注意审题 注意特判
*不要红温 不要急躁 耐心一点
*WA了不要立马觉得是思路不对 先耐心找反例
*/

#define endl '\n'
#define dbg(x) cout<<#x<<endl;cout<<x<<endl;
#define vdbg(a) cout<<#a<<endl;for(auto x:a)cout<<x<<" ";cout<<endl;
#define YES cout<<"YES"<<endl;return ;
#define Yes cout<<"Yes"<<endl;return ;
#define NO cout<<"NO"<<endl;return ;
#define No cout<<"No"<<endl;return ;
#define popcount __builtin_popcount
using ll=long long;
using i128=__int128;
using ld=long double;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
const int INF=1e9;
const ll INFLL=1e18;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
const int ddx[]={-2,-1,1,2,2,1,-1,-2};
const int ddy[]={1,2,2,1,-1,-2,-2,-1};

struct DSU{
    vector<int>father;
    //自定义

    DSU(int n){
        father.assign(n,0);
        for(int i=0;i<n;i++){
            father[i]=i;

        }
    }

    int find(int i){
        if(i!=father[i]){
            father[i]=find(father[i]);
        }
        return father[i];
    }

    bool same(int x,int y){
        return find(x)==find(y);
    }

    bool merge(int x,int y){
        int fx=find(x);
        int fy=find(y);
        if(fx==fy){
            return false;
        }

        father[fx]=fy;
        
        return true;
    }
};

void solve()
{
    int n,m,q;
    cin>>n>>m>>q;
    vector<array<int,4>>edge(m+1);
    for(int i=1;i<=m;i++)
    {
        cin>>edge[i][0]>>edge[i][1]>>edge[i][2];
        edge[i][3]=i;
    }

    sort(edge.begin()+1,edge.end(),[&](auto &x,auto &y)
    {
        return x[2]>y[2];
    });

    vector<int>edgeToTree(m+1);
    int cnt=n;
    DSU dsu(2*n);
    vector<vector<int>>g(2*n);
    vector<int>key(2*n);
    for(int i=1;i<=m;i++)
    {
        auto [x,y,w,id]=edge[i];
        int fx=dsu.find(x);
        int fy=dsu.find(y);
        if(fx!=fy)
        {
            dsu.father[fx]=dsu.father[fy]=++cnt;
            key[cnt]=w;
            g[cnt].push_back(fx);
            g[cnt].push_back(fy);

            edgeToTree[id]=cnt;
        }
    }

    int MAXP=20;
    vector<int>dep(2*n);
    vector<vector<int>>stjump(2*n,vector<int>(MAXP+1));
    vector<int>leaf(2*n);

    auto dfs=[&](auto &&self,int u,int fa)->void
    {
        dep[u]=dep[fa]+1;
        stjump[u][0]=fa;
        for(int p=1;p<=MAXP;p++)
        {
            stjump[u][p]=stjump[stjump[u][p-1]][p-1];
        }
        
        leaf[u]=(u<=n);

        for(auto v:g[u]){
            if(v!=fa){
                self(self,v,u);

                leaf[u]+=leaf[v];
            }
        }
    };
    for(int i=1;i<=cnt;i++)
    {
        if(i==dsu.father[i])
        {
            dfs(dfs,i,0);
        }
    }
    
    int limit=0;

    auto query=[&](int u)->int
    {
        for(int p=MAXP;p>=0;p--)
        {
            if(stjump[u][p]>0&&key[stjump[u][p]]>=limit)
            {
                u=stjump[u][p];
            }
        }
        return leaf[u];
    };

    queue<pii>que;
    int op,x,y;
    while(q--)
    {
        cin>>op;
        if(op==1)
        {
            cin>>limit;
            while(!que.empty())
            {
                auto [id,val]=que.front();
                que.pop();

                key[edgeToTree[id]]=val;
            }
        }
        else if(op==2)
        {
            cin>>x;
            cout<<query(x)<<endl;
        }
        else if(op==3)
        {
            cin>>x>>y;
            
            if(edgeToTree[x])
            {
                que.push({x,y});
            }
        }
    }
}

void init()
{
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    init();
    while(t--)
    {
        solve();    
    }
    return 0;
}

首先，因为只能走大于等于 limit 的边，那么也就是说边权越小越难走到。所以考虑对边权从大到小排序，此时构建的重构树就保证了小的边权一定在上方，即连通的最小边权的最大值。那么用 st 表维护一下跳到的节点，每次判断跳往点的点权是否小于 limit，考察其子树内的叶子个数即可。

对于修改操作，乍一看会觉得没法处理，因为修改一次就会导致重构树发生变化。但题目保证了不管怎么修改，边权的排名都不会变。所以不管边权怎么变，对于某一条边，其在不在重构树上的状态是不会改变的。所以就只需要记一下每条边在重构树上的节点编号，每次直接修改即可。

3.D - Stamp Rally

#include <bits/stdc++.h>
using namespace std;

/*   /\_/\
*   (= ._.)
*   / >  \>
*/

/*
*想好再写
*注意审题 注意特判
*不要红温 不要急躁 耐心一点
*WA了不要立马觉得是思路不对 先耐心找反例
*/

#define endl '\n'
#define dbg(x) cout<<#x<<endl;cout<<x<<endl;
#define vdbg(a) cout<<#a<<endl;for(auto x:a)cout<<x<<" ";cout<<endl;
#define YES cout<<"YES"<<endl;return ;
#define Yes cout<<"Yes"<<endl;return ;
#define NO cout<<"NO"<<endl;return ;
#define No cout<<"No"<<endl;return ;
#define popcount __builtin_popcount
using ll=long long;
using i128=__int128;
using ld=long double;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
const int INF=1e9;
const ll INFLL=1e18;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
const int ddx[]={-2,-1,1,2,2,1,-1,-2};
const int ddy[]={1,2,2,1,-1,-2,-2,-1};

struct DSU{
    vector<int>father;
    //自定义

    DSU(int n){
        father.assign(n,0);
        for(int i=0;i<n;i++){
            father[i]=i;

        }
    }

    int find(int i){
        if(i!=father[i]){
            father[i]=find(father[i]);
        }
        return father[i];
    }

    bool same(int x,int y){
        return find(x)==find(y);
    }

    bool merge(int x,int y){
        int fx=find(x);
        int fy=find(y);
        if(fx==fy){
            return false;
        }

        father[fx]=fy;
        
        return true;
    }
};

void solve()
{
    int n,m;
    cin>>n>>m;
    vector<array<int,3>>edge(m+1);
    for(int i=1;i<=m;i++)
    {
        cin>>edge[i][0]>>edge[i][1];
        edge[i][2]=i;
    }

    sort(edge.begin()+1,edge.end(),[&](auto &x,auto &y)
    {
        return x[2]<y[2];
    });

    int cnt=n;
    DSU dsu(2*n);
    vector<vector<int>>g(2*n);
    vector<int>key(2*n);
    for(int i=1;i<=m;i++)
    {
        auto [x,y,w]=edge[i];
        int fx=dsu.find(x);
        int fy=dsu.find(y);
        if(fx!=fy)
        {
            dsu.father[fx]=dsu.father[fy]=++cnt;
            key[cnt]=w;
            g[cnt].push_back(fx);
            g[cnt].push_back(fy);

        }
    }

    int MAXP=20;
    vector<int>dep(2*n);
    vector<vector<int>>stjump(2*n,vector<int>(MAXP+1));
    vector<int>leaf(2*n);

    auto dfs=[&](auto &&self,int u,int fa)->void
    {
        dep[u]=dep[fa]+1;
        stjump[u][0]=fa;
        for(int p=1;p<=MAXP;p++)
        {
            stjump[u][p]=stjump[stjump[u][p-1]][p-1];
        }

        leaf[u]=(u<=n);

        for(auto v:g[u]){
            if(v!=fa){
                self(self,v,u);
                leaf[u]+=leaf[v];
            }
        }
    };
    for(int i=1;i<=cnt;i++)
    {
        if(i==dsu.father[i])
        {
            dfs(dfs,i,0);
        }
    }

    auto check=[&](int x,int y,int z,int limit)->bool
    {
        for(int p=MAXP;p>=0;p--)
        {
            if(stjump[x][p]>0&&key[stjump[x][p]]<=limit)
            {
                x=stjump[x][p];
            }
            if(stjump[y][p]>0&&key[stjump[y][p]]<=limit)
            {
                y=stjump[y][p];
            }
        }

        if(x==y)
        {
            return leaf[x]>=z;
        }
        return leaf[x]+leaf[y]>=z;
    };

    int q;
    cin>>q;
    int x,y,z;
    while(q--)
    {
        cin>>x>>y>>z;

        int l=1;
        int r=m;
        int mid;
        int ans;
        while(l<=r)
        {
            mid=l+r>>1;
            if(check(x,y,z,mid))
            {
                ans=mid;
                r=mid-1;
            }
            else
            {
                l=mid+1;
            }
        }
        cout<<ans<<endl;
    }
}

void init()
{
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    init();
    while(t--)
    {
        solve();    
    }
    return 0;
}

虽然这道题里没有边权，但由于要求走过边的最大编号尽可能小，所以考虑将边的编号作为边权赋给每条边，之后再从小到大构建重构树即可。之后可以发现，虽然要求恰好经过 z 个点，但若当前连通区域内有超过 z 个点，此时肯定是可以达成的，因为可以不走多余的点。

在每次查询的时候，可以发现答案存在单调性。若当前答案可以达成，那么选大于当前答案的边必然也可以达成条件，而若当前答案没法达成，那么就说明更小的答案必然也无法达成。所以就可以考虑二分答案，每次去重构树上倍增找小于等于当前答案能走到的节点个数即可。

注意因为是从 x 和 y 出发，一开始两个点分属不同连通块时，能走到的点的个数是要相加的。而在两点处于同一个连通块后，此时就只能算这一个大连通块个数了。

4.归程

这个题纯粹缝合怪……

#include <bits/stdc++.h>
using namespace std;

/*   /\_/\
*   (= ._.)
*   / >  \>
*/

/*
*想好再写
*注意审题 注意特判
*不要红温 不要急躁 耐心一点
*WA了不要立马觉得是思路不对 先耐心找反例
*/

#define endl '\n'
#define dbg(x) cout<<#x<<endl;cout<<x<<endl;
#define vdbg(a) cout<<#a<<endl;for(auto x:a)cout<<x<<" ";cout<<endl;
#define YES cout<<"YES"<<endl;return ;
#define Yes cout<<"Yes"<<endl;return ;
#define NO cout<<"NO"<<endl;return ;
#define No cout<<"No"<<endl;return ;
#define popcount __builtin_popcount
using ll=long long;
using i128=__int128;
using ld=long double;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
const int INF=1e9;
const ll INFLL=1e18;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
const int ddx[]={-2,-1,1,2,2,1,-1,-2};
const int ddy[]={1,2,2,1,-1,-2,-2,-1};

struct DSU{
    vector<int>father;
    //自定义

    DSU(int n){
        father.assign(n,0);
        for(int i=0;i<n;i++){
            father[i]=i;

        }
    }

    int find(int i){
        if(i!=father[i]){
            father[i]=find(father[i]);
        }
        return father[i];
    }

    bool same(int x,int y){
        return find(x)==find(y);
    }

    bool merge(int x,int y){
        int fx=find(x);
        int fy=find(y);
        if(fx==fy){
            return false;
        }

        father[fx]=fy;
        
        return true;
    }
};

void solve()
{
    int n,m;
    cin>>n>>m;
    vector<array<ll,4>>edge(m+1);
    vector<vector<pll>>g(n+1);
    for(int i=1,u,v,l,a;i<=m;i++)
    {
        cin>>u>>v>>l>>a;
        g[u].push_back({v,l});
        g[v].push_back({u,l});
        edge[i]={u,v,l,a};
    }

    vector<ll>dis(n+1,INFLL);
    vector<int>vis(n+1);

    auto dijkstra=[&](int s)->void {
        auto cmp=[&](array<ll,2>&x,array<ll,2>&y)->bool {
            return x[1]>y[1];
        };

        priority_queue<array<ll,2>,vector<array<ll,2>>,decltype(cmp)>heap(cmp);

        heap.push({s,0});
        dis[s]=0;
        
        while(!heap.empty()){
            auto [u,_]=heap.top();
            heap.pop();

            if(vis[u]){
                continue;
            }

            vis[u]=1;
            for(auto [v,w]:g[u]){
                if(!vis[v]&&dis[u]+w<dis[v]){
                    dis[v]=dis[u]+w;
                    heap.push({v,dis[v]});
                }
            }
        }
    };

    dijkstra(1);

    sort(edge.begin()+1,edge.end(),[&](auto &x,auto &y)
    {
        return x[3]>y[3];
    });

    int cnt=n;
    DSU dsu(2*n);
    vector<vector<int>>t(2*n);
    vector<int>key(2*n);
    for(int i=1;i<=m;i++)
    {
        auto [x,y,l,a]=edge[i];
        int fx=dsu.find(x);
        int fy=dsu.find(y);
        if(fx!=fy)
        {
            dsu.father[fx]=dsu.father[fy]=++cnt;
            key[cnt]=a;
            t[cnt].push_back(fx);
            t[cnt].push_back(fy);

        }
    }

    int MAXP=20;
    vector<int>dep(2*n);
    vector<vector<int>>stjump(2*n,vector<int>(MAXP+1));
    vector<ll>minDis(2*n,INFLL);

    auto dfs=[&](auto &&self,int u,int fa)->void
    {
        dep[u]=dep[fa]+1;
        stjump[u][0]=fa;
        for(int p=1;p<=MAXP;p++)
        {
            stjump[u][p]=stjump[stjump[u][p-1]][p-1];
        }

        if(u<=n)
        {
            minDis[u]=dis[u];
        }

        for(auto v:t[u]){
            if(v!=fa){
                self(self,v,u);

                minDis[u]=min(minDis[u],minDis[v]);
            }
        }
    };
    for(int i=1;i<=cnt;i++)
    {
        if(i==dsu.father[i])
        {
            dfs(dfs,i,0);
        }
    }

    auto query=[&](int u,int limit)->ll
    {
        for(int p=MAXP;p>=0;p--)
        {
            if(stjump[u][p]>0&&key[stjump[u][p]]>limit)
            {
                u=stjump[u][p];
            }
        }
        return minDis[u];
    };

    int q,k,s;
    cin>>q>>k>>s;
    int v,p;
    int pre=0;
    while(q--)
    {
        cin>>v>>p;
        v=(v+k*pre-1)%n+1;
        p=(p+k*pre)%(s+1);

        pre=query(v,p);
        cout<<pre<<endl;
    }
}

void init()
{
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    init();
    while(t--)
    {
        solve();    
    }
    return 0;
}

首先，只能走边权大于 limit 这个问题可以通过重构树解决。那么对于此时划分出来的连通块，就要求所有叶子节点的点到 1 的最短距离。那么这个就可以通过从 1 出发跑一遍 dijkstra 解决，维护出重构树上每个点内部叶子节点 dis 表的最小值即可。

5.E. Qpwoeirut and Vertices

区间 lca 终于讲了！！之前自己学没咋学明白，左神伟大！！

#include <bits/stdc++.h>
using namespace std;

/*   /\_/\
*   (= ._.)
*   / >  \>
*/

/*
*想好再写
*注意审题 注意特判
*不要红温 不要急躁 耐心一点
*WA了不要立马觉得是思路不对 先耐心找反例
*/

#define endl '\n'
#define dbg(x) cout<<#x<<endl;cout<<x<<endl;
#define vdbg(a) cout<<#a<<endl;for(auto x:a)cout<<x<<" ";cout<<endl;
#define YES cout<<"YES"<<endl;return ;
#define Yes cout<<"Yes"<<endl;return ;
#define NO cout<<"NO"<<endl;return ;
#define No cout<<"No"<<endl;return ;
#define popcount __builtin_popcount
using ll=long long;
using i128=__int128;
using ld=long double;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
const int INF=1e9;
const ll INFLL=1e18;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
const int ddx[]={-2,-1,1,2,2,1,-1,-2};
const int ddy[]={1,2,2,1,-1,-2,-2,-1};

struct DSU{
    vector<int>father;
    //自定义

    DSU(int n){
        father.assign(n,0);
        for(int i=0;i<n;i++){
            father[i]=i;

        }
    }

    int find(int i){
        if(i!=father[i]){
            father[i]=find(father[i]);
        }
        return father[i];
    }

    bool same(int x,int y){
        return find(x)==find(y);
    }

    bool merge(int x,int y){
        int fx=find(x);
        int fy=find(y);
        if(fx==fy){
            return false;
        }

        father[fx]=fy;
        
        return true;
    }
};

void solve()
{
    int n,m,q;
    cin>>n>>m>>q;
    vector<array<int,3>>edge(m+1);
    for(int i=1;i<=m;i++)
    {
        cin>>edge[i][0]>>edge[i][1];
        edge[i][2]=i;
    }

    sort(edge.begin()+1,edge.end(),[&](auto &x,auto &y)
    {
        return x[2]<y[2];
    });

    int cnt=n;
    DSU dsu(2*n);
    vector<vector<int>>g(2*n);
    vector<int>key(2*n);
    for(int i=1;i<=m;i++)
    {
        auto [x,y,w]=edge[i];
        int fx=dsu.find(x);
        int fy=dsu.find(y);
        if(fx!=fy)
        {
            dsu.father[fx]=dsu.father[fy]=++cnt;
            key[cnt]=w;
            g[cnt].push_back(fx);
            g[cnt].push_back(fy);

        }
    }

    int MAXP=20;
    vector<int>dep(2*n);
    vector<vector<int>>stjump(2*n,vector<int>(MAXP+1));
    vector<int>dfn(2*n);
    vector<int>seg(2*n);
    int cntd=0;

    auto dfs=[&](auto &&self,int u,int fa)->void
    {
        dep[u]=dep[fa]+1;
        stjump[u][0]=fa;
        for(int p=1;p<=MAXP;p++)
        {
            stjump[u][p]=stjump[stjump[u][p-1]][p-1];
        }

        dfn[u]=++cntd;
        seg[cntd]=u;

        for(auto v:g[u]){
            if(v!=fa){
                self(self,v,u);

            }
        }
    };
    for(int i=1;i<=cnt;i++)
    {
        if(i==dsu.father[i])
        {
            dfs(dfs,i,0);
        }
    }

    vector<int>lg2(2*n);
    vector<vector<int>>stmin(2*n,vector<int>(MAXP+1));
    vector<vector<int>>stmax(2*n,vector<int>(MAXP+1));
    lg2[0]=-1;
    for(int i=1;i<=n;i++)
    {
        lg2[i]=lg2[i>>1]+1;
        stmax[i][0]=dfn[i];
        stmin[i][0]=dfn[i];
    }
    for(int p=1;p<=lg2[n];p++)
    {
        for(int i=1;i+(1<<p)-1<=n;i++)
        {
            stmax[i][p]=max(stmax[i][p-1],stmax[i+(1<<(p-1))][p-1]);
            stmin[i][p]=min(stmin[i][p-1],stmin[i+(1<<(p-1))][p-1]);
        }
    }

    auto queryLCA=[&](int a,int b)->int
    {
        if(dep[a]<dep[b]){
            swap(a,b);
        }
    
        //自定义

        for(int p=MAXP;p>=0;p--){
            if(dep[stjump[a][p]]>=dep[b]){
                a=stjump[a][p];
            }
        }
    
        if(a==b){
            return a;
        }
    
        for(int p=MAXP;p>=0;p--){
            if(stjump[a][p]!=stjump[b][p]){
                a=stjump[a][p];
                b=stjump[b][p];
            }
        }

        return stjump[a][0];
    };

    auto query=[&](int l,int r)->int
    {
        int p=lg2[r-l+1];
        int mn=min(stmin[l][p],stmin[r-(1<<p)+1][p]);
        int mx=max(stmax[l][p],stmax[r-(1<<p)+1][p]);

        int x=seg[mn];
        int y=seg[mx];
        int lca=queryLCA(x,y);
        return key[lca];
    };

    int l,r;
    while(q--)
    {
        cin>>l>>r;
        cout<<query(l,r)<<" ";
    }
    cout<<endl;
}

void init()
{
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    init();
    while(t--)
    {
        solve();    
    }
    return 0;
}

这道题跟之前的题一样，还是按边的编号赋权，唯一不同的就是查的是区间 lca。

那么对于查一个点集中点的 lca，就是找出这些点中 dfn 序最小和最大的点，点集的 lca 就是这两个点的 lca。这个是因为 dfn 序越小代表在越左侧的位置，越大代表在越大的位置，所以两者的 lca 就可以覆盖整个点集了。那么就是给重构树分配 dfn 序，然后每次查 dfn 序的范围最值，再映射回重构树，最后查 lca 即可。范围最值还是可以用 st 表维护，当然无脑线段树也可以（）

6.D. Graph and Queries

这个题太妙了！！

#include <bits/stdc++.h>
using namespace std;

/*   /\_/\
*   (= ._.)
*   / >  \>
*/

/*
*想好再写
*注意审题 注意特判
*不要红温 不要急躁 耐心一点
*WA了不要立马觉得是思路不对 先耐心找反例
*/

#define endl '\n'
#define dbg(x) cout<<#x<<endl;cout<<x<<endl;
#define vdbg(a) cout<<#a<<endl;for(auto x:a)cout<<x<<" ";cout<<endl;
#define YES cout<<"YES"<<endl;return ;
#define Yes cout<<"Yes"<<endl;return ;
#define NO cout<<"NO"<<endl;return ;
#define No cout<<"No"<<endl;return ;
#define popcount __builtin_popcount
using ll=long long;
using i128=__int128;
using ld=long double;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
const int INF=1e9;
const ll INFLL=1e18;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
const int ddx[]={-2,-1,1,2,2,1,-1,-2};
const int ddy[]={1,2,2,1,-1,-2,-2,-1};

struct DSU{
    vector<int>father;
    //自定义

    DSU(int n){
        father.assign(n,0);
        for(int i=0;i<n;i++){
            father[i]=i;

        }
    }

    int find(int i){
        if(i!=father[i]){
            father[i]=find(father[i]);
        }
        return father[i];
    }

    bool same(int x,int y){
        return find(x)==find(y);
    }

    bool merge(int x,int y){
        int fx=find(x);
        int fy=find(y);
        if(fx==fy){
            return false;
        }

        father[fx]=fy;
        
        return true;
    }
};

template<typename T>
struct Segment_Tree
{
    vector<T>data;
    //自定义
    const vector<T>&p;
    const vector<int>&seg;

    Segment_Tree(){}

    Segment_Tree(int n,const vector<T>&p,const vector<int>&seg):p(p),seg(seg){
        data.assign(n<<2,0);
    }

    //初始全0不用build
    void build(int l,int r,int i)
    {
        if(l==r){
            //自定义
            data[i]=l;
        }   
        else{
            int m=(l+r)>>1;
            build(l,m,i<<1);
            build(m+1,r,i<<1|1);
            up(i);
        }
        //自定义

    }

    void change(int jobl,int jobr,T jobv,int l,int r,int i){
        if(jobl<=l&&r<=jobr){
            data[i]=jobv;
        }
        else{
            int m=(l+r)>>1;

            if(jobl<=m){
                change(jobl,jobr,jobv,l,m,i<<1);
            }
            if(m+1<=jobr){
                change(jobl,jobr,jobv,m+1,r,i<<1|1);
            }

            up(i);
        }
    }

    T query(int jobl,int jobr,int l,int r,int i){
        if(jobl<=l&&r<=jobr){
            return data[i];
        }
        
        int m=(l+r)>>1;

        //自定义
        T ans=0;
        if(jobl<=m){
            int res=query(jobl,jobr,l,m,i<<1);
            if(p[seg[res]]>p[seg[ans]])
            {
                ans=res;
            }
        }
        if(m+1<=jobr){
            int res=query(jobl,jobr,m+1,r,i<<1|1);
            if(p[seg[res]]>p[seg[ans]])
            {
                ans=res;
            }
        }

        return ans;
    }

    //自定义
    void up(int i){
        if(p[seg[data[i<<1]]]>p[seg[data[i<<1|1]]])
        {
            data[i]=data[i<<1];
        }
        else
        {
            data[i]=data[i<<1|1];
        }
    }
};

void solve()
{
    int n,m,q;
    cin>>n>>m>>q;
    vector<int>p(n+1);
    for(int i=1;i<=n;i++)
    {
        cin>>p[i];
    }
    vector<array<int,4>>edge(m+1);
    for(int i=1;i<=m;i++)
    {
        cin>>edge[i][0]>>edge[i][1];
        edge[i][3]=i;
    }
    vector<array<int,2>>oper(q+1);
    for(int i=1;i<=q;i++)
    {
        cin>>oper[i][0]>>oper[i][1];
    }

    for(int i=1;i<=q;i++)
    {
        if(oper[i][0]==2)
        {
            edge[oper[i][1]][2]=-1;
        }
    }

    int cntw=0;
    for(int i=1;i<=m;i++)
    {
        if(edge[i][2]!=-1)
        {
            edge[i][2]=++cntw;
        }
    }
    for(int i=q;i>=1;i--)
    {
        if(oper[i][0]==2)
        {
            edge[oper[i][1]][2]=++cntw;
        }
    }

    sort(edge.begin()+1,edge.end(),[&](auto &x,auto &y)
    {
        return x[2]<y[2];
    });

    int cnt=n;
    DSU dsu(2*n);
    vector<vector<int>>g(2*n);
    vector<int>key(2*n);
    for(int i=1;i<=m;i++)
    {
        auto [x,y,w,id]=edge[i];
        int fx=dsu.find(x);
        int fy=dsu.find(y);
        if(fx!=fy)
        {
            dsu.father[fx]=dsu.father[fy]=++cnt;
            key[cnt]=w;
            g[cnt].push_back(fx);
            g[cnt].push_back(fy);

        }
    }

    int MAXP=20;
    vector<int>dep(2*n);
    vector<vector<int>>stjump(2*n,vector<int>(MAXP+1));
    int cntd=0;
    vector<int>dfn(n+1);
    vector<int>seg(n+1);
    vector<int>leafSiz(2*n);
    vector<int>leafMin(2*n,INF);

    auto dfs=[&](auto &&self,int u,int fa)->void
    {
        dep[u]=dep[fa]+1;
        stjump[u][0]=fa;
        for(int p=1;p<=MAXP;p++)
        {
            stjump[u][p]=stjump[stjump[u][p-1]][p-1];
        }

        if(u<=n)
        {
            dfn[u]=++cntd;
            seg[cntd]=u;
            leafSiz[u]=1;
            leafMin[u]=cntd;
        }

        for(auto v:g[u]){
            if(v!=fa){
                self(self,v,u);

                leafSiz[u]+=leafSiz[v];
                leafMin[u]=min(leafMin[u],leafMin[v]);
            }
        }
    };
    for(int i=1;i<=cnt;i++)
    {
        if(i==dsu.father[i])
        {
            dfs(dfs,i,0);
        }
    }

    auto queryLCA=[&](int u,int limit)->int
    {
        for(int p=MAXP;p>=0;p--)
        {
            if(stjump[u][p]>0&&key[stjump[u][p]]<=limit)
            {
                u=stjump[u][p];
            }
        }
        return u;
    };

    Segment_Tree<int>st(n+1,p,seg);
    st.build(1,n,1);

    int limit=m;
    for(int i=1;i<=q;i++)
    {
        auto [op,x]=oper[i];

        if(op==1)
        {
            int lca=queryLCA(x,limit);

            int res=st.query(leafMin[lca],leafMin[lca]+leafSiz[lca]-1,1,n,1);
            cout<<p[seg[res]]<<endl;
            if(res)
            {
                st.change(res,res,0,1,n,1);
            }
        }
        else
        {
            limit--;
        }
    }
}

void init()
{
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    init();
    while(t--)
    {
        solve();    
    }
    return 0;
}

首先，考虑将所有操作离线下来。之后先把要删除的边统计出来，在忽略这些边的基础上，按编号从小到大，给剩下的边从 1 开始分配边权。在上图例子中，就是先忽略 2 号 3 号和 4 号边，然后给 1 号和 5 号边分别分配 1 和 2 的边权。

之后再考虑这些被删掉的边，此时考虑倒序给这些边分配边权。那么在上图例子中，就是先给 4 号边分配边权 3，再给 2 号边分配边权 4，最后给 3 号边分配边权 5。在这样操作后，此时就可以通过边权的大小来判断删除的先后顺序了，边权更大的边必然在更早的时候被删除。

此时从小到大建出重构树，考虑维护一个 limit 变量，初始为边的个数 m。每次在碰到删除操作时，直接让 limit 减一。此时在查询的时候，就可以查从 x 出发只经过小于等于 limit 的边，能到达的连通区域了。这个是因为边权就很好地维护了删除的顺序，对于每个时刻，大于 limit 的边就说明在之前被删除了。此时就可以像之前一样，通过 st 表每次找到对应连通块的子树了。

此时就需要考虑子树查询和修改问题了。对于子树这个范围查询问题，还是考虑用线段树维护。那么就是先只对叶子节点分配 dfn 序，然后用线段树维护 dfn 序范围中，拥有最大点权的 dfn 序即可。而为了每次快速找到子树内叶子节点的范围，考虑再让重构树的每个节点维护其内部的最小 dfn 序和内部的叶子数量，此时每次就可以通过这个最小的 dfn 序和叶子的数量划定在线段树内的范围了。

这个将删除的先后顺序转化为边权利用其单调性的思路太妙了！！

7.Peaks 加强版

#include <bits/stdc++.h>
using namespace std;

/*   /\_/\
*   (= ._.)
*   / >  \>
*/

/*
*想好再写
*注意审题 注意特判
*不要红温 不要急躁 耐心一点
*WA了不要立马觉得是思路不对 先耐心找反例
*/

#define endl '\n'
#define dbg(x) cout<<#x<<endl;cout<<x<<endl;
#define vdbg(a) cout<<#a<<endl;for(auto x:a)cout<<x<<" ";cout<<endl;
#define YES cout<<"YES"<<endl;return ;
#define Yes cout<<"Yes"<<endl;return ;
#define NO cout<<"NO"<<endl;return ;
#define No cout<<"No"<<endl;return ;
#define popcount __builtin_popcount
using ll=long long;
using i128=__int128;
using ld=long double;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
const int INF=1e9;
const ll INFLL=1e18;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
const int ddx[]={-2,-1,1,2,2,1,-1,-2};
const int ddy[]={1,2,2,1,-1,-2,-2,-1};

struct DSU{
    vector<int>father;
    //自定义

    DSU(int n){
        father.assign(n,0);
        for(int i=0;i<n;i++){
            father[i]=i;

        }
    }

    int find(int i){
        if(i!=father[i]){
            father[i]=find(father[i]);
        }
        return father[i];
    }

    bool same(int x,int y){
        return find(x)==find(y);
    }

    bool merge(int x,int y){
        int fx=find(x);
        int fy=find(y);
        if(fx==fy){
            return false;
        }

        father[fx]=fy;
        
        return true;
    }
};

template<typename T>
struct Persistent_SegTree{
    vector<int>root;
    vector<int>left;
    vector<int>right;
    vector<T>data;
    int cnt;

    //自定义

    Persistent_SegTree(){}

    //n: number of version, 0-based
    //m: length of single tree, 0-based
    Persistent_SegTree(int n,int m){
        root.assign(n,0);
        left.assign(m*70,0);
        right.assign(m*70,0);
        data.assign(m*70,0);
        cnt=0;

        //自定义
    }

    //自定义
    int build(int l,int r){
        int cur=++cnt;
        data[cur]=0;

        if(l==r){

        }
        else{
            int m=l+r>>1;
            left[cur]=build(l,m);
            right[cur]=build(m+1,r);
        }
        return cur;
    }

    //单点修改
    int change(int jobi,T jobv,int l,int r,int i){
        int cur=copy(i);
        data[cur]+=jobv;

        if(l==r){
            
        }
        else{
            int m=l+r>>1;
            if(jobi<=m){
                left[cur]=change(jobi,jobv,l,m,left[cur]);
            }
            else{
                right[cur]=change(jobi,jobv,m+1,r,right[cur]);
            }
        }
        return cur;
    }

    //区间 [u,v] 查第 k 大
    int kth(int jobk,int l,int r,int u,int v){
        if(l==r){
            return l;
        }
        
        int cnt=data[right[v]]-data[right[u]];
        int m=l+r>>1;
        if(cnt<jobk){
            return kth(jobk-cnt,l,m,left[u],left[v]);
        }
        else{
            return kth(jobk,m+1,r,right[u],right[v]);
        }
    }

    //自定义
    int copy(int i){
        int cur=++cnt;
        left[cur]=left[i];
        right[cur]=right[i];
        data[cur]=data[i];

        //自定义

        return cur;
    }
};

void solve()
{
    int n,m,q;
    cin>>n>>m>>q;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }

    vector<int>sorted=a;
    sort(sorted.begin()+1,sorted.end());
    int len=1;
    for(int i=2;i<=n;i++)
    {
        if(sorted[len]!=sorted[i])
        {
            sorted[++len]=sorted[i];
        }
    }
    auto rnk=[&](int v)->int
    {
        int l=1;
        int r=len;
        int m;
        int ans;
        while(l<=r)
        {
            m=l+r>>1;
            if(sorted[m]>=v)
            {
                ans=m;
                r=m-1;
            }
            else
            {
                l=m+1;
            }
        }
        return ans;
    };
    for(int i=1;i<=n;i++)
    {
        a[i]=rnk(a[i]);
    }

    vector<array<int,3>>edge(m+1);
    for(int i=1;i<=m;i++)
    {
        cin>>edge[i][0]>>edge[i][1]>>edge[i][2];
    }

    sort(edge.begin()+1,edge.end(),[&](auto &x,auto &y)
    {
        //自定义
        return x[2]<y[2];
    });

    int cnt=n;
    DSU dsu(2*n);
    vector<vector<int>>g(2*n);
    vector<int>key(2*n);
    for(int i=1;i<=m;i++)
    {
        auto [x,y,w]=edge[i];
        int fx=dsu.find(x);
        int fy=dsu.find(y);
        if(fx!=fy)
        {
            dsu.father[fx]=dsu.father[fy]=++cnt;
            key[cnt]=w;
            g[cnt].push_back(fx);
            g[cnt].push_back(fy);

        }
    }

    int MAXP=20;
    vector<int>dep(2*n);
    vector<vector<int>>stjump(2*n,vector<int>(MAXP+1));
    int cntd=0;
    vector<int>dfn(n+1);
    vector<int>seg(n+1);
    vector<int>leafSiz(2*n);
    vector<int>leafMin(2*n,INF);

    auto dfs=[&](auto &&self,int u,int fa)->void
    {
        dep[u]=dep[fa]+1;
        stjump[u][0]=fa;
        for(int p=1;p<=MAXP;p++)
        {
            stjump[u][p]=stjump[stjump[u][p-1]][p-1];
        }

        if(u<=n)
        {
            dfn[u]=++cntd;
            seg[cntd]=u;
            leafSiz[u]=1;
            leafMin[u]=cntd;
        }

        for(auto v:g[u]){
            if(v!=fa){
                self(self,v,u);

                leafSiz[u]+=leafSiz[v];
                leafMin[u]=min(leafMin[u],leafMin[v]);
            }
        }
    };
    for(int i=1;i<=cnt;i++)
    {
        if(i==dsu.father[i])
        {
            dfs(dfs,i,0);
        }
    }

    Persistent_SegTree<int>st(n+1,len+1);
    st.root[0]=st.build(1,len);
    for(int i=1;i<=n;i++)
    {
        st.root[i]=st.change(a[seg[i]],1,1,len,st.root[i-1]);
    }

    auto queryLCA=[&](int u,int limit)->int
    {
        for(int p=MAXP;p>=0;p--)
        {
            if(stjump[u][p]>0&&key[stjump[u][p]]<=limit)
            {
                u=stjump[u][p];
            }
        }
        return u;
    };

    int u,limit,k;
    int pre=0;
    while(q--)
    {
        cin>>u>>limit>>k;
        u=(u^pre)%n+1,k=(k^pre)%n+1,limit=limit^pre;

        int lca=queryLCA(u,limit);

        if(leafSiz[lca]<k)
        {
            pre=0;
            cout<<-1<<endl;
            continue;
        }

        int rk=st.kth(k,1,len,st.root[leafMin[lca]-1],st.root[leafMin[lca]+leafSiz[lca]-1]);
        pre=sorted[rk];
        cout<<pre<<endl;
    }
}

void init()
{
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    init();
    while(t--)
    {
        solve();    
    }
    return 0;
}

首先，看到第 k 大很自然就能想到用主席树。而又因为边权又要求小于等于 limit，那么就是构建重构树，然后在树上构建主席树即可。

这里有一个重要的理解。对于 kruskal 重构树，不仅可以将其看作一棵树进行树上倍增，还可以利用 dfn 序单纯考察叶子节点，也就是将所有叶子节点看作一个一维数组。

那么和上道题类似，还是在重构树的每个节点维护内部最小的 dfn 序和内部的叶子数量，这样就可以快速在主席树上定位查询区间了。那么对于子树内的第 k 大，只需要在每次给叶子节点分配 dfn 序的时候建立新版本的线段树，之后每次查询的时候就可以通过两个版本二分了。

这码量太吓人了……

总结

感觉 kruskal 重构树最妙的就是把图上具有单调性的问题转化成树上问题，然后对于树上问题，就可以用倍增维护了。有的时候还可以通过 dfn 序将叶子节点拍到数组上，再结合线段树之类的进行子树，即连通块的查询。

END