Codeforces

Luogu

分析

首先有一个结论：一个大小为偶数的连通块一定存在一个合法的边集，一个大小为奇数的连通块一定不存在一个合法的边集。

证明：

• 如果连通块大小为奇数，又因为每个点度数都为奇数，所以总度数为奇数，这是不可能的。
• 如果连通块大小为偶数，此时我们可以先找到一棵生成树，从下往上构造即可。可以发现一定能构造出解。

于是我们只需要保证图中没有大小为奇数的连通块即可。

考虑一个类似 Kruskal 的思路，即按边权从小到大加入所有边，直到满足条件。

于是我们可以用 LCT 维护生成森林，用堆维护所有生成森林中的边。加入一条边时，首先替换掉路径上最大边，然后每次从堆中弹出一条边权最大的边并删除，直到删除这条边后不满足条件，这条边就是答案。

具体还要求每个连通块大小，用维护子树信息那套维护一下虚子树大小即可。

代码

// ===================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=400000+10;

int n,m,X[N],Y[N],Z[N];
priority_queue<pair<int,int> > Q;

#define ls(x) ch[x][0]
#define rs(x) ch[x][1]
int fa[N],ch[N][2],w[N],mx[N],sz[N],lsz[N],del[N],rev[N],sta[N],cnt;
int nroot(int x) { return ls(fa[x])==x||rs(fa[x])==x; }
void pushup(int x) {
    sz[x]=sz[ls(x)]+sz[rs(x)]+lsz[x]+(x<=n);
    int y=w[mx[ls(x)]]>w[mx[rs(x)]]?mx[ls(x)]:mx[rs(x)];
    mx[x]=w[x]>w[y]?x:y;
}
void pushdown(int x) {
    if (rev[x]) {
        if (ls(x)) rev[ls(x)]^=1,swap(ls(ls(x)),rs(ls(x)));
        if (rs(x)) rev[rs(x)]^=1,swap(ls(rs(x)),rs(rs(x)));
        rev[x]=0;
    }
}
void rotate(int x) {
    int y=fa[x],z=fa[y],k=(x==rs(y)),w=ch[x][!k];
    if (nroot(y)) ch[z][y==rs(z)]=x;
    ch[x][!k]=y,ch[y][k]=w;
    if (w) fa[w]=y; fa[y]=x,fa[x]=z;
    pushup(y);
}
void splay(int x) {
    int y=x,z=0; sta[++z]=y;
    while (nroot(y)) sta[++z]=y=fa[y];
    while (z) pushdown(sta[z--]);
    while (nroot(x)) {
        y=fa[x],z=fa[y];
        if (nroot(y)) rotate((x==ls(y)^(y==ls(z)))?x:y);
        rotate(x);
    }
    pushup(x);
}
void access(int x) {
    for (int y=0;x;x=fa[y=x])
        splay(x),lsz[x]+=sz[rs(x)],lsz[x]-=sz[rs(x)=y],pushup(x);
}
void makeroot(int x) { access(x),splay(x),rev[x]^=1,swap(ls(x),rs(x)); }
int findroot(int x) {
    access(x),splay(x);
    while (ls(x)) pushdown(x),x=ls(x);
    return x;
}
void split(int x,int y) { makeroot(x),access(y),splay(y); }
void link(int x,int y) {
    makeroot(x),access(y),splay(y); cnt-=sz[x]&1,cnt-=sz[y]&1;
    lsz[fa[x]=y]+=sz[x],pushup(y); cnt+=sz[y]&1;
}
void cut(int x,int y) {
    split(x,y); cnt-=sz[y]&1;
    fa[x]=ls(y)=0,pushup(y); cnt+=sz[x]&1,cnt+=sz[y]&1;
}

int solve(int i) {
    int x=X[i],y=Y[i],z=Z[i];
    if (findroot(x)==findroot(y)) {
        split(x,y); int p=mx[y];
        if (w[p]>z) {
            del[p-n]=1; sz[i+n]=1,w[i+n]=z,mx[i+n]=i+n;
            cut(X[p-n],p),cut(Y[p-n],p);
            link(x,i+n),link(y,i+n);
            Q.push(make_pair(z,i));
        }
    } else {
        sz[i+n]=1,w[i+n]=z,mx[i+n]=i+n;
        link(x,i+n),link(y,i+n);
        Q.push(make_pair(z,i));
    }
    if (cnt) return -1;
    while (!Q.empty()) {
        int p=Q.top().second; Q.pop();
        if (del[p]) continue;
        cut(X[p],p+n),cut(Y[p],p+n);
        if (cnt) {
            Q.push(make_pair(Z[p],p));
            link(X[p],p+n),link(Y[p],p+n);
            return Z[p];
        }
    }
    return 0;
}

int main() {
    cnt=n=read(),m=read();
    for (int i=1;i<=n;++i) sz[i]=1,mx[i]=i;
    for (int i=1;i<=m;++i) {
        X[i]=read(),Y[i]=read(),Z[i]=read();
        printf("%d\n",solve(i));
    }
    return 0;
}