XCPC Notes

Appearance

发布时间：2025-04-08

动态树 ​

概念 ​

  • 每个点最多有一条实边
  • splay维护所有实边路径
  • 中序遍历维护路径
  • 虚边用每个splay根节点维护
  • 虚边：子节点知道父节点是谁，但是父节点不知道子节点
  • 实边：互相已知
  • access(x)从根节点建立一条到x的实边路径
    • 从下往上做，先把x旋转到splay的根，假设他的虚边父亲是y，把y旋转到其对应的splay根节点
    • 因为中序遍历的原因，y的右子树必定为空，x插到y的最右子树即可
  • makeroot(x)将x变成根
    • 先access(x)，然后将x旋转到splay根，再翻转路径
  • findroot(x)找到x所在树的根节点
    • 先access(x)，然后将找到splay的最左侧点
  • split(x,y)将x到y变成实边路径
    • 先makeroot(x),再access(y)
  • link(x,y)如果x,y不连通，则加一条边
    • makeroot(x)，x指向y
  • cut(x,y)如果x,y有边，删除
    • makeroot(x)看y是不是后继
  • isroot(x)判断x是否是所在splay的根节点
cpp
namespace LCT{
    /*
    记住操作的必须严格是森林
    isroot(x):判断x是否为根节点
    access(x):在x所在连通块上建一条从根到x的路径
    make_root(x):将x所在连通块的根变为x
    findroot(x):找到x所在连通块的根
    split(x,y):将x和y所在连通块的路径建一条splay树
    link(x,y):添加边
    cut(x,y):删边
    */
    static constexpr int INF=LLONG_MAX; 
    struct Node{
        Node *fa,*son[2];
        int val,sz,rev;
        Node(int _v=0,Node *_fa=nullptr,int _cnt=1):fa(_fa),son{nullptr,nullptr},val(_v),sz(1){
            rev=0;
        }
    };
    vector<Node*> stk;
    #define son(x,y) (x->son[y])
    void pushrev(Node *u){
        if(u==nullptr)return;
        u->rev^=1;
        swap(son(u,0),son(u,1));
    }
    void pushup(Node *u){
        if(!u)return;
        u->sz=1;
        if(son(u,0)){
            u->sz+=son(u,0)->sz;
        }
        if(son(u,1)){
            u->sz+=son(u,1)->sz;
        }
    }
    void pushdown(Node *u){
        if(u->rev){
            pushrev(son(u,0));
            pushrev(son(u,1));
            u->rev=0;
        }
    }
    bool isroot(Node *u){
        if(u->fa==nullptr)return true;
        return son(u->fa,0)!=u&&son(u->fa,1)!=u;
    }
    void rotate(Node *x){
        auto y=x->fa,z=y->fa;
        int d=(x==son(y,1));// 0: left, 1: right
        if(z&&y&&!isroot(y))son(z,y==son(z,1))=x;
        x->fa=z;
        if(y)son(y,d)=son(x,d^1),y->fa=x;
        if(son(x,d^1))son(x,d^1)->fa=y;
        x->son[d^1]=y;
        pushup(y);
        pushup(x);
    }
    void splay(Node *x){
        Node *r=x;
        stk.clear();
        stk.push_back(r);
        while(!isroot(r)){
            stk.push_back(r->fa);
            r=r->fa;
        }
        while(stk.size()){
            pushdown(stk.back());
            stk.pop_back();
        }
        while(!isroot(x)){
            Node *y=x->fa,*z=y->fa;
            if(!isroot(y)){
                if((x==son(y,1))==(y==son(z,1)))rotate(y);
                else rotate(x);
            }
            rotate(x);
        }
    }
    void access(Node *x){// 建立从根到x的路径，同时x变成根
        Node *z=x,*y=nullptr;
        while(x){
            splay(x);
            x->son[1]=y;
            pushup(x);
            y=x;
            x=x->fa;
        }
        splay(z);
    }
    void make_root(Node *x){// 使x为根
        access(x);
        pushrev(x);
    }
    Node* findroot(Node *x){// 找到x的根节点，再将原树的根节点变成splay的根节点
        access(x);
        while(son(x,0))pushdown(x),x=son(x,0);
        splay(x);
        return x;
    }
    void split(Node *x,Node *y){// 给x和y的路径建立splay,x为根
        make_root(y);
        access(x);
    }
    void link(Node *x,Node *y){// 连接y->x
        make_root(y);
        if(findroot(x)!=y)y->fa=x;
    }
    void cut(Node *x,Node *y){// 断开x和y的连接
        make_root(x);
        if(findroot(y)==x&&y->fa==x&&son(y,0)==nullptr){
            y->fa=nullptr;
            son(x,1)=nullptr;
            pushup(x);
        }
    }
    #undef son
}
using namespace LCT;
void solve(){
    int n,m;
    cin>>n>>m;
    vector<Node*> a(n+1);
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        a[i]=new Node(x);
    }
    while(m--){
        int op,x,y;
        cin>>op>>x>>y;
        if(op==0){
            split(a[x],a[y]);
            cout<<a[x]->sum<<'\n';
        }
        else if(op==1)link(a[x],a[y]);
        else if(op==2)cut(a[x],a[y]);
        else{
            splay(a[x]);
            a[x]->val=y;
            pushup(a[x]);
        }
    }
}

维护链信息 ​

P2387 [NOI2014] 魔法森林 ​

求从1-n的代价最小，代价为max⁡(A1,A2,....)+max⁡(B1,B2,....)\max(A_1,A_2,....)+\max(B_1,B_2,....)A,B是边的两个值

  • 按A排序，从小到大枚举A，然后就是求1-n的最小B代价
  • 拆点，边拆成一个点，有一个权值
  • 维护森林
cpp
namespace LCT{
    /*
    记住操作的必须严格是森林
    isroot(x):判断x是否为根节点
    access(x):在x所在连通块上建一条从根到x的路径
    make_root(x):将x所在连通块的根变为x
    findroot(x):找到x所在连通块的根
    split(x,y):将x和y所在连通块的路径建一条splay树
    link(x,y):添加边
    cut(x,y):删边
    */
    struct Node{
        Node *fa,*son[2];
        int val,sz,cnt,rev;
        Node *mx;
        Node(int _v=0,Node *_fa=nullptr,int _cnt=1):fa(_fa),son{nullptr,nullptr},val(_v),sz(1),cnt(_cnt){
            rev=0;
            mx=this;
        }
    };
    vector<Node*> stk;
    #define son(x,y) (x->son[y])
    void pushrev(Node *u){
        if(u==nullptr)return;
        u->rev^=1;
        swap(son(u,0),son(u,1));
    }
    void pushup(Node *u){
        if(!u)return;
        u->sz=u->cnt;
        u->mx=u;
        if(son(u,0)){
            u->sz+=son(u,0)->sz;
            if(son(u,0)->mx->val>u->mx->val)u->mx=son(u,0)->mx;
        }
        if(son(u,1)){
            u->sz+=son(u,1)->sz;
            if(son(u,1)->mx->val>u->mx->val)u->mx=son(u,1)->mx;
        }
    }
    void pushdown(Node *u){
        if(u->rev){
            pushrev(son(u,0));
            pushrev(son(u,1));
            u->rev=0;
        }
    }
    bool isroot(Node *u){
        if(u->fa==nullptr)return true;
        return son(u->fa,0)!=u&&son(u->fa,1)!=u;
    }
    void rotate(Node *x){
        auto y=x->fa,z=y->fa;
        int d=(x==son(y,1));// 0: left, 1: right
        if(z&&y&&!isroot(y))son(z,y==son(z,1))=x;
        x->fa=z;
        if(y)son(y,d)=son(x,d^1),y->fa=x;
        if(son(x,d^1))son(x,d^1)->fa=y;
        x->son[d^1]=y;
        pushup(y);
        pushup(x);
    }
    void splay(Node *x){
        Node *r=x;
        stk.clear();
        stk.push_back(r);
        while(!isroot(r)){
            stk.push_back(r->fa);
            r=r->fa;
        }
        while(stk.size()){
            pushdown(stk.back());
            stk.pop_back();
        }
        while(!isroot(x)){
            Node *y=x->fa,*z=y->fa;
            if(!isroot(y)){
                if((x==son(y,1))==(y==son(z,1)))rotate(y);
                else rotate(x);
            }
            rotate(x);
        }
    }
    void access(Node *x){// 建立从根到x的路径，同时x变成根
        Node *z=x,*y=nullptr;
        while(x){
            splay(x);
            x->son[1]=y;
            pushup(x);
            y=x;
            x=x->fa;
        }
        splay(z);
    }
    void make_root(Node *x){// 使x为根
        access(x);
        pushrev(x);
    }
    Node* findroot(Node *x){// 找到x的根节点，再将原树的根节点变成splay的根节点
        access(x);
        while(son(x,0))pushdown(x),x=son(x,0);
        splay(x);
        return x;
    }
    void split(Node *x,Node *y){// 给x和y的路径建立splay,x为根
        make_root(y);
        access(x);
    }
    void link(Node *x,Node *y){// 连接y->x
        make_root(y);
        if(findroot(x)!=y)y->fa=x;
    }
    void cut(Node *x,Node *y){// 断开x和y的连接
        make_root(x);
        if(findroot(y)==x&&y->fa==x&&son(y,0)==nullptr){
            y->fa=nullptr;
            son(x,1)=nullptr;
            pushup(x);
        }
    }
    #undef son
}
using namespace LCT;
void solve(){
    int n,m;
    cin>>n>>m;
    vector<Node*> a(n+m+1);
    vector<array<int,4>> e(m);
    for(auto &[x,y,A,B]:e){
        cin>>x>>y>>A>>B;
    }
    sort(e.begin(),e.end(),[](auto &x,auto &y){
        return x[2]<y[2];
    });
    map<Node*,vector<Node*>> edges;
    for(int i=1;i<=n+m;i++){
        a[i]=new Node(0);
        if(i>n)a[i]->val=e[i-n-1][3],edges[a[i]].push_back(a[e[i-n-1][0]]),edges[a[i]].push_back(a[e[i-n-1][1]]);
    }
    int ans=INF;
    for(int i=1;i<=m;i++){
        auto [x,y,A,B]=e[i-1];
        if(findroot(a[x])==findroot(a[y])){
            split(a[x],a[y]);
            auto now=a[x]->mx;
            if(now->val>B){
                for(auto &i:edges[now]){
                    cut(now,i);
                }
            }
        }
        link(a[x],a[i+n]);
        link(a[y],a[i+n]);
        if(findroot(a[1])==findroot(a[n])){
            split(a[1],a[n]);
            auto now=a[1]->mx;
            ans=min(ans,A+now->val);
        }
    }
    cout<<(ans==INF?-1:ans)<<'\n';
}

P1501 [国家集训队] Tree II ​

一棵 nn 个点的树，每个点的初始权值为 11。
对于这棵树有 qq 个操作，每个操作为以下四种操作之一：

  • + u v c：将 uu 到 vv 的路径上的点的权值都加上自然数 cc；
  • - u1 v1 u2 v2：将树中原有的边 (u1,v1)(u_1,v_1) 删除，加入一条新边 (u2,v2)(u_2,v_2)，保证操作完之后仍然是一棵树；
  • * u v c：将 uu 到 vv 的路径上的点的权值都乘上自然数 cc；
  • / u v：询问 uu 到 vv 的路径上的点的权值和，将答案对 5106151061 取模。
cpp
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define F first
#define S second
#define TR tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
typedef pair<int,int> PII;
const int N=2e6+10,M=2e5+10;
const int INF=1e18;
// const int mod=998244353;
// const int mod=1e9+7;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
struct mint {
    const static int mod = 51061;
	int x;
	inline mint(int o = 0) { x = o; }
	inline mint & operator = (int o) { return x = o, *this; }
	inline mint & operator += (mint o) { return (x += o.x) >= mod && (x -= mod), *this; }
	inline mint & operator -= (mint o) { return (x -= o.x) < 0 && (x += mod), *this; }
	inline mint & operator *= (mint o) { return x = (long long) x * o.x % mod, *this; }
    inline mint& qpow(int b){
        mint w = *this;
        mint ret(1);
        for(; b; b >>= 1, w *= w) if(b & 1) ret *= w;
        return x = ret.x, *this;
    }
	inline mint & operator /= (mint o) { return *this *= (o .qpow( (mod - 2))); }
	friend inline mint operator + (mint a, mint b) { return a += b; }
	friend inline mint operator - (mint a, mint b) { return a -= b; }
	friend inline mint operator * (mint a, mint b) { return a *= b; }
	friend inline mint operator / (mint a, mint b) { return a /= b; }
    friend ostream& operator<<(ostream& os, const mint& m) {
        return os << m.x;
    }
};
namespace LCT{
    /*
    记住操作的必须严格是森林
    isroot(x):判断x是否为根节点
    access(x):在x所在连通块上建一条从根到x的路径
    make_root(x):将x所在连通块的根变为x
    findroot(x):找到x所在连通块的根
    split(x,y):将x和y所在连通块的路径建一条splay树
    link(x,y):添加边
    cut(x,y):删边
    */
    struct Node{
        Node *fa,*son[2];
        int sz,rev;
        mint val,sum,mul,add;
        Node(int _v=0,Node *_fa=nullptr):fa(_fa),son{nullptr,nullptr},val(_v),sz(1){
            rev=0;
            sum=val;
            mul=1;
            add=0;
        }
    };
    vector<Node*> stk;
    #define son(x,y) (x->son[y])
    void pushrev(Node *u){
        if(u==nullptr)return;
        u->rev^=1;
        swap(son(u,0),son(u,1));
    }
    void pushmul(Node *u,mint x){
        if(u==nullptr)return;
        u->mul*=x;
        u->add*=x;
        u->val*=x;
        u->sum*=x;
    }
    void pushadd(Node *u,mint x){
        if(u==nullptr)return;
        u->add+=x;
        u->val+=x;
        u->sum+=x*u->sz;
    }
    void pushup(Node *u){
        if(!u)return;
        u->sz=1;
        u->sum=u->val;
        if(son(u,0)){
            u->sz+=son(u,0)->sz;
            u->sum+=son(u,0)->sum;
        }
        if(son(u,1)){
            u->sz+=son(u,1)->sz;
            u->sum+=son(u,1)->sum;
        }
    }
    void pushdown(Node *u){
        if(u->rev){
            pushrev(son(u,0));
            pushrev(son(u,1));
            u->rev=0;
        }
        pushmul(son(u,0),u->mul);
        pushmul(son(u,1),u->mul);
        u->mul=1;
        pushadd(son(u,0),u->add);
        pushadd(son(u,1),u->add);
        u->add=0;
    }
    bool isroot(Node *u){
        if(u->fa==nullptr)return true;
        return son(u->fa,0)!=u&&son(u->fa,1)!=u;
    }
    void rotate(Node *x){
        auto y=x->fa,z=y->fa;
        int d=(x==son(y,1));// 0: left, 1: right
        if(z&&y&&!isroot(y))son(z,y==son(z,1))=x;
        x->fa=z;
        if(y)son(y,d)=son(x,d^1),y->fa=x;
        if(son(x,d^1))son(x,d^1)->fa=y;
        x->son[d^1]=y;
        pushup(y);
        pushup(x);
    }
    void splay(Node *x){
        Node *r=x;
        stk.clear();
        stk.push_back(r);
        while(!isroot(r)){
            stk.push_back(r->fa);
            r=r->fa;
        }
        while(stk.size()){
            pushdown(stk.back());
            stk.pop_back();
        }
        while(!isroot(x)){
            Node *y=x->fa,*z=y->fa;
            if(!isroot(y)){
                if((x==son(y,1))==(y==son(z,1)))rotate(y);
                else rotate(x);
            }
            rotate(x);
        }
    }
    void access(Node *x){// 建立从根到x的路径，同时x变成根
        Node *z=x,*y=nullptr;
        while(x){
            splay(x);
            x->son[1]=y;
            pushup(x);
            y=x;
            x=x->fa;
        }
        splay(z);
    }
    void make_root(Node *x){// 使x为根
        access(x);
        pushrev(x);
    }
    Node* findroot(Node *x){// 找到x的根节点，再将原树的根节点变成splay的根节点
        access(x);
        while(son(x,0))pushdown(x),x=son(x,0);
        splay(x);
        return x;
    }
    void split(Node *x,Node *y){// 给x和y的路径建立splay,x为根
        make_root(y);
        access(x);
    }
    void link(Node *x,Node *y){// 连接y->x
        make_root(y);
        if(findroot(x)!=y)y->fa=x;
    }
    void cut(Node *x,Node *y){// 断开x和y的连接
        make_root(x);
        if(findroot(y)==x&&y->fa==x&&son(y,0)==nullptr){
            y->fa=nullptr;
            son(x,1)=nullptr;
            pushup(x);
        }
    }
    #undef son
}
using namespace LCT;
void solve(){
    int n,q;
    cin>>n>>q;
    vector<Node*> a(n+1);
    for(int i=1;i<=n;i++)a[i]=new Node(1);
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        link(a[u],a[v]);
    }
    split(a[1],a[1]);
    while(q--){
        char op;
        int u,v,x,y;
        cin>>op;
        if(op=='+'){
            cin>>u>>v>>x;
            split(a[u],a[v]);
            pushadd(a[u],x);
            splay(a[u]);
        }
        else if(op=='-'){
            cin>>u>>v>>x>>y;
            cut(a[u],a[v]); 
            link(a[x],a[y]);
        }
        else if(op=='*'){
            cin>>u>>v>>x;
            split(a[u],a[v]);
            pushmul(a[u],x);
            splay(a[u]);
            pushup(a[u]);
        }
        else if(op=='/'){
            cin>>u>>v;
            split(a[u],a[v]);
            cout<<a[u]->sum<<'\n';
        }
    }
}

P3203 [HNOI2010] 弹飞绵羊 ​

某天，Lostmonkey 发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。

游戏一开始，Lostmonkey 在地上沿着一条直线摆上 nn 个装置，每个装置设定初始弹力系数 kik_i，当绵羊达到第 ii 个装置时，它会往后弹 kik_i 步，达到第 i+kii+k_i 个装置，若不存在第 i+kii+k_i 个装置，则绵羊被弹飞。

绵羊想知道当它从第 ii 个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey 可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。

  • 建立虚点n+1
  • 对min⁡(i+ki,n+1)\min(i+k_i,n+1)建边
  • 查询x→n+1x \rightarrow n+1的大小
cpp
namespace LCT{
    /*
    记住操作的必须严格是森林
    isroot(x):判断x是否为根节点
    access(x):在x所在连通块上建一条从根到x的路径
    make_root(x):将x所在连通块的根变为x
    findroot(x):找到x所在连通块的根
    split(x,y):将x和y所在连通块的路径建一条splay树
    link(x,y):添加边
    cut(x,y):删边
    */
    struct Node{
        Node *fa,*son[2];
        int sz,rev;
        int val;
        Node(int _v=0,Node *_fa=nullptr):fa(_fa),son{nullptr,nullptr},val(_v),sz(1){
            rev=0;
        }
    };
    vector<Node*> stk;
    #define son(x,y) (x->son[y])
    void pushrev(Node *u){
        if(u==nullptr)return;
        u->rev^=1;
        swap(son(u,0),son(u,1));
    }

    void pushup(Node *u){
        if(!u)return;
        u->sz=1;
        if(son(u,0)){
            u->sz+=son(u,0)->sz;
        }
        if(son(u,1)){
            u->sz+=son(u,1)->sz;
        }
    }
    void pushdown(Node *u){
        if(u->rev){
            pushrev(son(u,0));
            pushrev(son(u,1));
            u->rev=0;
        }
    }
    bool isroot(Node *u){
        if(u->fa==nullptr)return true;
        return son(u->fa,0)!=u&&son(u->fa,1)!=u;
    }
    void rotate(Node *x){
        auto y=x->fa,z=y->fa;
        int d=(x==son(y,1));// 0: left, 1: right
        if(z&&y&&!isroot(y))son(z,y==son(z,1))=x;
        x->fa=z;
        if(y)son(y,d)=son(x,d^1),y->fa=x;
        if(son(x,d^1))son(x,d^1)->fa=y;
        x->son[d^1]=y;
        pushup(y);
        pushup(x);
    }
    void splay(Node *x){
        Node *r=x;
        stk.clear();
        stk.push_back(r);
        while(!isroot(r)){
            stk.push_back(r->fa);
            r=r->fa;
        }
        while(stk.size()){
            pushdown(stk.back());
            stk.pop_back();
        }
        while(!isroot(x)){
            Node *y=x->fa,*z=y->fa;
            if(!isroot(y)){
                if((x==son(y,1))==(y==son(z,1)))rotate(y);
                else rotate(x);
            }
            rotate(x);
        }
    }
    void access(Node *x){// 建立从根到x的路径，同时x变成根
        Node *z=x,*y=nullptr;
        while(x){
            splay(x);
            x->son[1]=y;
            pushup(x);
            y=x;
            x=x->fa;
        }
        splay(z);
    }
    void make_root(Node *x){// 使x为根
        access(x);
        pushrev(x);
    }
    Node* findroot(Node *x){// 找到x的根节点，再将原树的根节点变成splay的根节点
        access(x);
        while(son(x,0))pushdown(x),x=son(x,0);
        splay(x);
        return x;
    }
    void split(Node *x,Node *y){// 给x和y的路径建立splay,x为根
        make_root(y);
        access(x);
    }
    void link(Node *x,Node *y){// 连接y->x
        make_root(y);
        if(findroot(x)!=y)y->fa=x;
    }
    void cut(Node *x,Node *y){// 断开x和y的连接
        make_root(x);
        if(findroot(y)==x&&y->fa==x&&son(y,0)==nullptr){
            y->fa=nullptr;
            son(x,1)=nullptr;
            pushup(x);
        }
    }
    #undef son
}
using namespace LCT;
void solve(){
    int n;
    cin>>n;
    vector<Node*> a(n+2);
    vector<int> b(n+1);
    for(int i=1;i<=n+1;i++)a[i]=new Node(0);
    for(int i=1;i<=n;i++){
        cin>>b[i];
        link(a[i],a[min(i+b[i],n+1)]);
    }
    int q;
    cin>>q;
    while(q--){
        int op,x,y;
        cin>>op>>x;
        x++;
        if(op==1){
            split(a[n+1],a[x]);
            cout<<a[n+1]->sz-1<<"\n";
        }
        else{
            cin>>y;
            cut(a[x],a[min(x+b[x],n+1)]);
            b[x]=y;
            link(a[x],a[min(x+b[x],n+1)]);

        }
    }

}

动态维护连通性&双连通分量 ​

P2147 [SDOI2008] 洞穴勘测 ​

加边，删边，询问是否在同一连通块

直接做

P3950 部落冲突 ​

维护双连通分量

cpp
namespace LCT{
    struct DSU{
        vector<int> par,siz;
        DSU(){}
        DSU(int n){init(n);}
        void init(int n){
            par.resize(n);
            iota(par.begin(),par.end(),0);
            siz.assign(n,1);
        }
        int find(int x){return par[x]==x?x:par[x]=find(par[x]);}
        bool merge(int x,int y){
            x=find(x),y=find(y);
            if(x==y)return false;
            siz[x]+=siz[y];
            par[y]=x;
            return true;
        }
        int size(int x){return siz[find(x)];}
        bool same(int x,int y){return find(x)==find(y);}
    } dcc;
    /*
    记住操作的必须严格是森林
    isroot(x):判断x是否为根节点
    access(x):在x所在连通块上建一条从根到x的路径
    make_root(x):将x所在连通块的根变为x
    findroot(x):找到x所在连通块的根
    split(x,y):将x和y所在连通块的路径建一条splay树
    link(x,y):添加边
    cut(x,y):删边
    */
    static constexpr int INF=LLONG_MAX; 
    struct Node{
        Node *fa,*son[2];
        int val,sz,rev;
        Node(int _v=0,Node *_fa=nullptr,int _cnt=1):fa(_fa),son{nullptr,nullptr},val(_v),sz(1){
            rev=0;
        }
    };
    vector<Node*> stk,a;
    #define son(x,y) (x->son[y])
    void pushrev(Node *u){
        if(u==nullptr)return;
        u->rev^=1;
        swap(son(u,0),son(u,1));
    }
    void pushup(Node *u){
        if(!u)return;
        u->sz=1;    
        if(son(u,0))u->sz+=son(u,0)->sz;
        if(son(u,1))u->sz+=son(u,1)->sz;
    }
    void pushdown(Node *u){
        if(u->rev){
            pushrev(son(u,0));
            pushrev(son(u,1));
            u->rev=0;
        }
    }
    bool isroot(Node *u){
        if(u->fa==nullptr)return true;
        return son(u->fa,0)!=u&&son(u->fa,1)!=u;
    }
    void rotate(Node *x){
        auto y=x->fa,z=y->fa;
        int d=(x==son(y,1));// 0: left, 1: right
        if(z&&y&&!isroot(y))son(z,y==son(z,1))=x;
        x->fa=z;
        if(y)son(y,d)=son(x,d^1),y->fa=x;
        if(son(x,d^1))son(x,d^1)->fa=y;
        x->son[d^1]=y;
        pushup(y);
        pushup(x);
    }
    void splay(Node *x){
        Node *r=x;
        stk.clear();
        stk.push_back(r);
        while(!isroot(r)){
            stk.push_back(r->fa);
            r=r->fa;
        }
        while(stk.size()){
            pushdown(stk.back());
            stk.pop_back();
        }
        while(!isroot(x)){
            Node *y=x->fa,*z=y->fa;
            if(!isroot(y)){
                if((x==son(y,1))==(y==son(z,1)))rotate(y);
                else rotate(x);
            }
            rotate(x);
        }
    }
    void access(Node *x){// 建立从根到x的路径，同时x变成根
        Node *z=x,*y=nullptr;
        while(x){
            splay(x);
            x->son[1]=y;
            pushup(x);
            y=x;
            if(x->fa){
                x=x->fa=a[dcc.find(x->fa->val)];// 重要改变
            }
            else x=x->fa;
        }
        splay(z);
    }
    void make_root(Node *x){// 使x为根
        access(x);
        pushrev(x);
    }
    Node* findroot(Node *x){// 找到x的根节点，再将原树的根节点变成splay的根节点
        access(x);
        while(son(x,0))pushdown(x),x=son(x,0);
        splay(x);
        return x;
    }
    void split(Node *x,Node *y){// 给x和y的路径建立splay,x为根
        make_root(y);
        access(x);
    }
    void del(Node *x,Node *y){
        if(!x)return;
        dcc.par[x->val]=y->val;
        del(son(x,0),y);
        del(son(x,1),y);
    }
    void link(Node *x,Node *y){// 连接y->x
        if(dcc.same(x->val,y->val))return;
        x=a[dcc.find(x->val)],y=a[dcc.find(y->val)];
        make_root(y);
        if(findroot(x)!=y)y->fa=x;
        else{
            del(son(y,1),y);
            son(y,1)=nullptr;
            pushup(y);
        }
    }
    void cut(Node *x,Node *y){// 断开x和y的连接
        make_root(x);
        if(findroot(y)==x&&y->fa==x&&son(y,0)==nullptr){
            y->fa=nullptr;
            son(x,1)=nullptr;
            pushup(x);
        }
    }
    void init(int n){
        dcc.init(n+1);
    }
    #undef son
}
using namespace LCT;
void solve(){
    int n,m;
    cin>>n>>m;
    init(n);
    a.assign(n+1,nullptr);
    for(int i=1;i<=n;i++)a[i]=new Node(i);
    vector<array<int,3>> e;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        if(u>v)swap(u,v);
        e.push_back({u,v,0});
    }
    vector<array<int,3>> que;
    vector<int> ans;
    ranges::sort(e);
    while(1){
        int op,u,v;
        cin>>op;
        if(op==-1)break;
        cin>>u>>v;
        if(u>v)swap(u,v);
        que.push_back({op,u,v});
        if(!op){
            auto it=lower_bound(e.begin(),e.end(),array<int,3>{u,v,0});
            (*it)[2]=1;
        }
    }
    for(auto [u,v,op]:e){
        if(!op)link(a[u],a[v]);
    }
    ranges::reverse(que);
    for(auto [op,u,v]:que){
        auto fu=a[dcc.find(u)],fv=a[dcc.find(v)];
        if(op==1){
            split(fu,fv);
            ans.push_back(fu->sz-1);
        }
        else{
            link(fu,fv);
        }
    }
    ranges::reverse(ans);
    for(auto x:ans){
        cout<<x<<'\n';
    }
}

P2542 [AHOI2005]航线规划 ​

离线下来，就变成只有加边

LCT维护边双连通分量 ​

cpp
namespace LCT{
    struct DSU{
        vector<int> par,siz;
        DSU(){}
        DSU(int n){init(n);}
        void init(int n){
            par.resize(n);
            iota(par.begin(),par.end(),0);
            siz.assign(n,1);
        }
        int find(int x){return par[x]==x?x:par[x]=find(par[x]);}
        bool merge(int x,int y){
            x=find(x),y=find(y);
            if(x==y)return false;
            siz[x]+=siz[y];
            par[y]=x;
            return true;
        }
        int size(int x){return siz[find(x)];}
        bool same(int x,int y){return find(x)==find(y);}
    } dcc;
    /*
    记住操作的必须严格是森林
    isroot(x):判断x是否为根节点
    access(x):在x所在连通块上建一条从根到x的路径
    make_root(x):将x所在连通块的根变为x
    findroot(x):找到x所在连通块的根
    split(x,y):将x和y所在连通块的路径建一条splay树
    link(x,y):添加边
    cut(x,y):删边
    */
    static constexpr int INF=LLONG_MAX; 
    struct Node{
        Node *fa,*son[2];
        int val,sz,rev;
        Node(int _v=0,Node *_fa=nullptr,int _cnt=1):fa(_fa),son{nullptr,nullptr},val(_v),sz(1){
            rev=0;
        }
    };
    vector<Node*> stk,a;
    #define son(x,y) (x->son[y])
    void pushrev(Node *u){
        if(u==nullptr)return;
        u->rev^=1;
        swap(son(u,0),son(u,1));
    }
    void pushup(Node *u){
        if(!u)return;
        u->sz=1;    
        if(son(u,0))u->sz+=son(u,0)->sz;
        if(son(u,1))u->sz+=son(u,1)->sz;
    }
    void pushdown(Node *u){
        if(u->rev){
            pushrev(son(u,0));
            pushrev(son(u,1));
            u->rev=0;
        }
    }
    bool isroot(Node *u){
        if(u->fa==nullptr)return true;
        return son(u->fa,0)!=u&&son(u->fa,1)!=u;
    }
    void rotate(Node *x){
        auto y=x->fa,z=y->fa;
        int d=(x==son(y,1));// 0: left, 1: right
        if(z&&y&&!isroot(y))son(z,y==son(z,1))=x;
        x->fa=z;
        if(y)son(y,d)=son(x,d^1),y->fa=x;
        if(son(x,d^1))son(x,d^1)->fa=y;
        x->son[d^1]=y;
        pushup(y);
        pushup(x);
    }
    void splay(Node *x){
        Node *r=x;
        stk.clear();
        stk.push_back(r);
        while(!isroot(r)){
            stk.push_back(r->fa);
            r=r->fa;
        }
        while(stk.size()){
            pushdown(stk.back());
            stk.pop_back();
        }
        while(!isroot(x)){
            Node *y=x->fa,*z=y->fa;
            if(!isroot(y)){
                if((x==son(y,1))==(y==son(z,1)))rotate(y);
                else rotate(x);
            }
            rotate(x);
        }
    }
    void access(Node *x){// 建立从根到x的路径，同时x变成根
        Node *z=x,*y=nullptr;
        while(x){
            splay(x);
            x->son[1]=y;
            pushup(x);
            y=x;
            if(x->fa){
                x=x->fa=a[dcc.find(x->fa->val)];// 重要改变
            }
            else x=x->fa;
        }
        splay(z);
    }
    void make_root(Node *x){// 使x为根
        access(x);
        pushrev(x);
    }
    Node* findroot(Node *x){// 找到x的根节点，再将原树的根节点变成splay的根节点
        access(x);
        while(son(x,0))pushdown(x),x=son(x,0);
        splay(x);
        return x;
    }
    void split(Node *x,Node *y){// 给x和y的路径建立splay,x为根
        make_root(y);
        access(x);
    }
    void del(Node *x,Node *y){
        if(!x)return;
        dcc.par[x->val]=y->val;
        dcc.siz[y->val]+=dcc.siz[x->val];
        del(son(x,0),y);
        del(son(x,1),y);
    }
    void link(Node *x,Node *y){// 连接y->x
        if(dcc.same(x->val,y->val))return;
        x=a[dcc.find(x->val)],y=a[dcc.find(y->val)];
        make_root(y);
        if(findroot(x)!=y)y->fa=x;
        else{
            del(son(y,1),y);
            son(y,1)=nullptr;
            pushup(y);
        }
    }
    void cut(Node *x,Node *y){// 断开x和y的连接
        make_root(x);
        if(findroot(y)==x&&y->fa==x&&son(y,0)==nullptr){
            y->fa=nullptr;
            son(x,1)=nullptr;
            pushup(x);
        }
    }
    void init(int n){
        dcc.init(n+1);
    }
    #undef son
}
using namespace LCT;
void solve(){
    int n,m;
    cin>>n>>m;
    init(n);
    a.assign(n+1,nullptr);
    for(int i=1;i<=n;i++)a[i]=new Node(i);
    vector<array<int,3>> e;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        if(u>v)swap(u,v);
        e.push_back({u,v,0});
    }
    vector<array<int,3>> que;
    vector<int> ans;
    ranges::sort(e);
    while(1){
        int op,u,v;
        cin>>op;
        if(op==-1)break;
        cin>>u>>v;
        if(u>v)swap(u,v);
        que.push_back({op,u,v});
        if(!op){
            auto it=lower_bound(e.begin(),e.end(),array<int,3>{u,v,0});
            (*it)[2]=1;
        }
    }
    for(auto [u,v,op]:e){
        if(!op)link(a[u],a[v]);
    }
    ranges::reverse(que);
    for(auto [op,u,v]:que){
        auto fu=a[dcc.find(u)],fv=a[dcc.find(v)];
        if(op==1){
            split(fu,fv);
            ans.push_back(fu->sz-1);
        }
        else{
            link(fu,fv);
        }
    }
    ranges::reverse(ans);
    for(auto x:ans){
        cout<<x<<'\n';
    }
}

P4172 [WC2006] 水管局长 ​

最短路的定义为一条路径的最大值最小，就可以用lct维护

cpp
namespace LCT{
    /*
    记住操作的必须严格是森林
    isroot(x):判断x是否为根节点
    access(x):在x所在连通块上建一条从根到x的路径
    make_root(x):将x所在连通块的根变为x
    findroot(x):找到x所在连通块的根
    split(x,y):将x和y所在连通块的路径建一条splay树
    link(x,y):添加边
    cut(x,y):删边
    */
    // static constexpr int INF=LLONG_MAX; 
    struct Node{
        Node *fa,*son[2];
        int val,sz,rev,id;
        Node *mn;
        Node(int _v=0,Node *_fa=nullptr,int _id=1):fa(_fa),son{nullptr,nullptr},val(_v),sz(1),id(_id){
            rev=0;
            mn=this;
        }
    };
    vector<Node*> stk;
    #define son(x,y) (x->son[y])
    void pushrev(Node *u){
        if(u==nullptr)return;
        u->rev^=1;
        swap(son(u,0),son(u,1));
    }
    void pushup(Node *u){
        if(!u)return;
        u->sz=1;
        u->mn=u;
        if(son(u,0)){
            u->sz+=son(u,0)->sz;
            if(u->mn->val<son(u,0)->mn->val)u->mn=son(u,0)->mn;
        }
        if(son(u,1)){
            u->sz+=son(u,1)->sz;
            if(u->mn->val<son(u,1)->mn->val)u->mn=son(u,1)->mn;
        }
    }
    void pushdown(Node *u){
        if(u->rev){
            pushrev(son(u,0));
            pushrev(son(u,1));
            u->rev=0;
        }
    }
    bool isroot(Node *u){
        if(u->fa==nullptr)return true;
        return son(u->fa,0)!=u&&son(u->fa,1)!=u;
    }
    void rotate(Node *x){
        auto y=x->fa,z=y->fa;
        int d=(x==son(y,1));// 0: left, 1: right
        if(z&&y&&!isroot(y))son(z,y==son(z,1))=x;
        x->fa=z;
        if(y)son(y,d)=son(x,d^1),y->fa=x;
        if(son(x,d^1))son(x,d^1)->fa=y;
        x->son[d^1]=y;
        pushup(y);
        pushup(x);
    }
    void splay(Node *x){
        Node *r=x;
        stk.clear();
        stk.push_back(r);
        while(!isroot(r)){
            stk.push_back(r->fa);
            r=r->fa;
        }
        while(stk.size()){
            pushdown(stk.back());
            stk.pop_back();
        }
        while(!isroot(x)){
            Node *y=x->fa,*z=y->fa;
            if(!isroot(y)){
                if((x==son(y,1))==(y==son(z,1)))rotate(y);
                else rotate(x);
            }
            rotate(x);
        }
    }
    void access(Node *x){// 建立从根到x的路径，同时x变成根
        Node *z=x,*y=nullptr;
        while(x){
            splay(x);
            x->son[1]=y;
            pushup(x);
            y=x;
            x=x->fa;
        }
        splay(z);
    }
    void make_root(Node *x){// 使x为根
        access(x);
        pushrev(x);
    }
    Node* findroot(Node *x){// 找到x的根节点，再将原树的根节点变成splay的根节点
        access(x);
        while(son(x,0))pushdown(x),x=son(x,0);
        splay(x);
        return x;
    }
    void split(Node *x,Node *y){// 给x和y的路径建立splay,x为根
        make_root(y);
        access(x);
    }
    void link(Node *x,Node *y){// 连接y->x
        make_root(y);
        if(findroot(x)!=y)y->fa=x;
    }
    void cut(Node *x,Node *y){// 断开x和y的连接
        make_root(x);
        if(findroot(y)==x&&y->fa==x&&son(y,0)==nullptr){
            y->fa=nullptr;
            son(x,1)=nullptr;
            pushup(x);
        }
    }
    #undef son
}
using namespace LCT;
struct DSU {
    std::vector<int> f, siz;
    
    DSU() {}
    DSU(int n) {
        init(n);
    }
    
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }
    
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    
    int size(int x) {
        return siz[find(x)];
    }
} dsu;
void solve(){
    int n,m,q;
    cin>>n>>m>>q;
    vector<Node*> a(n+1);
    for(int i=1;i<=n;i++)a[i]=new Node(-INF);
    map<PII,int> mp;
    vector<PII> edges;
    vector<Node*> enode;
    dsu.init(n+1);
    auto merge=[&](int x,int y,int t){
        if(x>y)swap(x,y);
        if(dsu.same(x,y)){
            split(a[x],a[y]);
            if(a[x]->mn->val<=t)return;
            int id=a[x]->mn->id;
            auto [L,R]=edges[id];
            cut(a[L],enode[id]);
            cut(a[R],enode[id]);
        }
        dsu.merge(x,y);
        int id=edges.size();
        edges.push_back({x,y});
        enode.push_back(new Node(t,nullptr,id));
        link(a[x],enode.back());
        link(a[y],enode.back());
    };
    vector<array<int,4>> e;
    for(int i=1;i<=m;i++){
        int u,v,t;
        cin>>u>>v>>t;
        if(u>v)swap(u,v);
        mp[{u,v}]=t;
        e.push_back({u,v,t,0});
    }
    ranges::sort(e);
    vector<array<int,3>> que;
    vector<int> ans;
    while(q--){
        int op,u,v;
        cin>>op>>u>>v;
        if(u>v)swap(u,v);
        que.push_back({op,u,v});
        if(op==2){
            auto it=lower_bound(e.begin(),e.end(),array<int,4>{u,v,0,0});
            (*it)[3]=1;
        }
    }
    for(auto [u,v,t,op]:e){
        if(!op)merge(u,v,t);
    }
    ranges::reverse(que);
    for(auto [op,u,v]:que){
        if(op==1){
            split(a[u],a[v]);
            ans.push_back(a[u]->mn->val);
        }
        else{
            auto t=mp[{u,v}];
            merge(u,v,t);
        }
    }
    ranges::reverse(ans);
    for(auto x:ans)cout<<x<<"\n";
}

UOJ274温暖会指引我们前行 ​

和P4172一样

P4180 [BJWC2010]次小生成树 ​

维护最大次大值，以及最小生成树，然后拿当前边的值替换掉生成边的最大值更新答案

P4234 最小差值生成树 ​

边权从小到大枚举，维护最大生成树，然后更新最大值-最小值，更新答案

cpp
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define F first
#define S second
#define TR tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
typedef pair<int,int> PII;
const int N=1e5+2,M=3e4+10;
const int INF=1e18;
const int mod=998244353;
// const int mod=1e9+7;k
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> val;
namespace LCT{
    /*
    记住操作的必须严格是森林
    isroot(x):判断x是否为根节点
    access(x):在x所在连通块上建一条从根到x的路径
    make_root(x):将x所在连通块的根变为x
    findroot(x):找到x所在连通块的根
    split(x,y):将x和y所在连通块的路径建一条splay树
    link(x,y):添加边
    cut(x,y):删边
    */
    struct Node{
        Node *fa,*son[2];
        int val,sz,rev;
        int id,mnid;
        Node(int _v=0,Node *_fa=nullptr,int _cnt=1):fa(_fa),son{nullptr,nullptr},val(_v),sz(1){
            rev=0;

        }
    };
    vector<Node*> stk;
    #define son(x,y) (x->son[y])
    void pushrev(Node *u){
        if(u==nullptr)return;
        u->rev^=1;
        swap(son(u,0),son(u,1));
    }
    void pushup(Node *u){
        if(!u)return;
        u->sz=1;
        u->mnid=u->id;
        for(int i=0;i<2;i++){
            if(son(u,i)){
                u->sz+=son(u,i)->sz;
                if(son(u,i)->mnid<u->mnid){
                    u->mnid=son(u,i)->mnid;
                }
            }
        }
    }
    void pushdown(Node *u){
        if(u->rev){
            pushrev(son(u,0));
            pushrev(son(u,1));
            u->rev=0;
        }
    }
    bool isroot(Node *u){
        if(u->fa==nullptr)return true;
        return son(u->fa,0)!=u&&son(u->fa,1)!=u;
    }
    void rotate(Node *x){
        auto y=x->fa,z=y->fa;
        int d=(x==son(y,1));// 0: left, 1: right
        if(z&&y&&!isroot(y))son(z,y==son(z,1))=x;
        x->fa=z;
        if(y)son(y,d)=son(x,d^1),y->fa=x;
        if(son(x,d^1))son(x,d^1)->fa=y;
        x->son[d^1]=y;
        pushup(y);
        pushup(x);
    }
    void splay(Node *x){
        Node *r=x;
        stk.clear();
        stk.push_back(r);
        while(!isroot(r)){
            stk.push_back(r->fa);
            r=r->fa;
        }
        while(stk.size()){
            pushdown(stk.back());
            stk.pop_back();
        }
        while(!isroot(x)){
            Node *y=x->fa,*z=y->fa;
            if(!isroot(y)){
                if((x==son(y,1))==(y==son(z,1)))rotate(y);
                else rotate(x);
            }
            rotate(x);
        }
    }
    void access(Node *x){// 建立从根到x的路径，同时x变成根
        Node *z=x,*y=nullptr;
        while(x){
            splay(x);
            x->son[1]=y;
            pushup(x);
            y=x;
            x=x->fa;
        }
        splay(z);
    }
    void make_root(Node *x){// 使x为根
        access(x);
        pushrev(x);
    }
    Node* findroot(Node *x){// 找到x的根节点，再将原树的根节点变成splay的根节点
        access(x);
        while(son(x,0))pushdown(x),x=son(x,0);
        splay(x);
        return x;
    }
    void split(Node *x,Node *y){// 给x和y的路径建立splay,x为根
        make_root(y);
        access(x);
    }
    void link(Node *x,Node *y){// 连接y->x
        make_root(y);
        if(findroot(x)!=y)y->fa=x;
    }
    void cut(Node *x,Node *y){// 断开x和y的连接
        make_root(x);
        if(findroot(y)==x&&y->fa==x&&son(y,0)==nullptr){
            y->fa=nullptr;
            son(x,1)=nullptr;
            pushup(x);
        }
    }
    #undef son
}
using namespace LCT;
struct DSU {
    std::vector<int> f, siz;
    
    DSU() {}
    DSU(int n) {
        init(n);
    }
    
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }
    
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    
    int size(int x) {
        return siz[find(x)];
    }
} dsu;
void solve(){
    int n,m;
    cin>>n>>m;
    vector<array<int,3>> edges(m);
    val=vector<int>(m+10,INF);
    for(auto &[w,u,v]:edges)cin>>u>>v>>w;
    ranges::sort(edges);
    dsu.init(n+1);
    vector<Node*> a(n+1),e(m+1);
    for(int i=1;i<=n;i++)a[i]=new Node(INF),a[i]->id=m;
    for(int i=0;i<m;i++){
        auto &[w,u,v]=edges[i];
        e[i]=new Node(w);
        e[i]->id=e[i]->mnid=i;
        val[i]=w;
    }
    multiset<int> s;
    int ans=INF;
    for(int i=0;i<m;i++){
        auto &[w,u,v]=edges[i];
        if(u==v)continue;
        if(dsu.merge(u,v)){
            link(a[u],e[i]);
            link(a[v],e[i]);
            s.insert(w);
        }
        else{
            split(a[u],a[v]);
            int id=a[u]->mnid;
            auto &[W,U,V]=edges[id];
            cut(a[U],e[id]);
            cut(a[V],e[id]);
            s.extract(W);
            link(a[u],e[i]);
            link(a[v],e[i]);
            s.insert(w);
        }
        if(s.size()==n-1)ans=min(ans,*s.rbegin()-*s.begin());
    }
    cout<<ans<<"\n";
}   
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T=1;
    // cin>>T;
    while(T--)solve();
    return 0;
}

P2387 [NOI2014] 魔法森林 ​

和P4172一样

Wenwei Lin · 2022 — 2025