【Codeforces 603E】Pastoral Oddities | Mrsrz's blog

LCT

题目大意：

给定一张无向图，边带权。依次加入 $m$ 条边。

每次加入一条边后，询问：

能否选出一个边的集合，使得每个点的度数都是奇数。能则输出这样的边集中，边权最大的边最小是多少。不能输出 $-1$。

题解：

有一个结论：

对一个大小为 $n$ 的连通块，若 $n$ 是偶数，则这个连通块中一定存在一种选边方案，使得连通块内每个点的度数都是奇数。反之则一定没有。

当 $n$ 是奇数时，由于总的度数是偶数，所以不可能每个点的度数是奇数。

当 $n$ 是偶数时，可以这样构造：

• 找一棵生成树，并选定一个根。
• 自底向上，对每个结点，考虑其儿子，如果其一个儿子的度数为偶数，则连上它与儿子之间的边。

这里当做到根时，由于存在奇数个度数为奇数的结点，所以根的度数也一定是奇数。

考虑什么情况下，大小为奇数的连通块会减少。

只有当两个奇数连通块连边时，这样的连通块个数才会减少 $2$。

考虑用 LCT 维护最小生成树，同时记录奇数连通块个数，并用一个 set 动态记录当前用了哪些边。

每次加入边的时候，如果两个点已经连通，则观察新加入的边能否替换最小生成树中的边，能则替换之。不改变奇偶性。

如果不连通，则连通之，并修改奇数连通块个数。

LCT 上需要维护链上边权最大值以及子树大小（奇偶性）。

执行完这些操作后，如果奇数连通块个数不为 $0$ 则输出 $-1$。

否则，我们考虑依次观察边权最大的边，看看是否能删掉。这里边已经用 set 排好序了。

如果删掉仍然满足条件，则删掉，否则不删，并输出最大边长。

正确性在于，一旦答案不为 $-1$，之后无论如何怎么加边，都不可能产生奇数连通块。故可以在满足条件的情况下随便删已有的边。

时间复杂度 $O(m\log m)$。

Code：

#include<iostream>
#include<algorithm>
#include<utility>
#include<set>
using namespace std;
const int N=4e5+5;
int n,m;
struct edge{
    int u,v,w;
}e[N];
namespace lct{
    int fa[N],ch[N][2],sz[N],val[N],sv[N],s_[N];
    pair<int,int>mx[N],dis[N];
    bool tag[N];
    inline bool ckr(int x,int p=1){return ch[fa[x]][p]==x;}
    inline bool isroot(int x){return!(ckr(x)||ckr(x,0));}
    inline void flip(int x){tag[x]^=1,swap(ch[x][0],ch[x][1]);}
    inline void update(int x){
        sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;
        sv[x]=sv[ch[x][0]]+sv[ch[x][1]]+s_[x]+val[x];
        mx[x]=max({dis[x],mx[ch[x][0]],mx[ch[x][1]]});
    }
    inline void pushdown(int x){
        if(tag[x]){
            if(ch[x][0])flip(ch[x][0]);
            if(ch[x][1])flip(ch[x][1]);
            tag[x]=0;
        }
    }
    inline void rotate(int x){
        int y=fa[x],z=fa[y],k=ckr(x);
        if(!isroot(y))ch[z][ckr(y)]=x;
        fa[y]=x,fa[x]=z,fa[ch[x][!k]]=y;
        ch[y][k]=ch[x][!k],ch[x][!k]=y,update(y);
    }
    inline void splay(int x){
        static int sta[N],top;sta[top=1]=x;
        for(int y=x;!isroot(y);sta[++top]=y=fa[y]);
        while(top)pushdown(sta[top--]);
        for(;!isroot(x);rotate(x))
        if(!isroot(fa[x]))rotate((ckr(x)^ckr(fa[x]))?x:fa[x]);
        update(x);
    }
    inline void access(int x){
        for(int t=0;x;ch[x][1]=t,t=x,x=fa[x])splay(x),s_[x]+=sv[ch[x][1]]-sv[t];
    }
    inline void makeroot(int x){access(x),splay(x),flip(x);}
    inline void split(int x,int y){makeroot(x),access(y),splay(y);}
    inline int findroot(int x){
        for(access(x),splay(x);ch[x][0];x=ch[x][0]);
        splay(x);return x;
    }
    inline bool connect(int x,int y){return findroot(x)==findroot(y);}
    inline void link(int x,int y){makeroot(x);if(findroot(y)!=x)makeroot(y),fa[x]=y,s_[y]+=sv[x];}
    inline void cut(int x,int y){split(x,y);if(ch[y][0]==x&&sz[x]==1)ch[y][0]=fa[x]=0,update(y);}
    pair<int,int>ask(int x,int y){
        split(x,y);
        return mx[y];
    }
    int get(int x){makeroot(x);return sv[x];}
}
set<pair<int,int> >st;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    lct::sz[i]=lct::val[i]=lct::sv[i]=1;
    for(int i=1;i<=m;++i){
        cin>>e[i].u>>e[i].v>>e[i].w;
        lct::sz[i+n]=1;
        lct::mx[i+n]=lct::dis[i+n]=make_pair(e[i].w,i);
    }
    int odd=n;
    for(int i=1;i<=m;++i){
        int u=e[i].u,v=e[i].v;
        if(lct::connect(u,v)){
            pair<int,int>qwq=lct::ask(u,v);
            if(e[i].w<qwq.first){
                int id=qwq.second;
                lct::cut(id+n,e[id].u);
                lct::cut(id+n,e[id].v);
                st.erase(make_pair(e[id].w,id));
                st.insert(make_pair(e[i].w,i));
                lct::link(i+n,u);
                lct::link(i+n,v);
            }
        }else{
            int _1=lct::get(u),_2=lct::get(v);
            if((_1&1)&&(_2&1))odd-=2;
            lct::link(i+n,u);
            lct::link(i+n,v);
            st.insert(make_pair(e[i].w,i));
        }
        if(odd)cout<<"-1\n";else{
            while(1){
                int id=st.rbegin()->second;
                lct::cut(id+n,e[id].u);
                lct::cut(id+n,e[id].v);
                int _1=lct::get(e[id].u),_2=lct::get(e[id].v);
                if((_1&1)&&(_2&1)){
                    lct::link(id+n,e[id].u);
                    lct::link(id+n,e[id].v);
                    cout<<st.rbegin()->first<<'\n';
                    break;
                }else st.erase(make_pair(e[id].w,id));
            }
        }
    }
    return 0;
}