给定一个 \(n\) 个结点的无向图，初始没有边。 接下来有 \(m\) 个询问，每次向图中加入一条连接 \((u, v)\) 权值为 \(w\) 的边。 每次加边后，查询是否存在一个边集 \(E\)，满足当图中只有 \(E\) 中的边时，所有点的度数均为奇数。 同时你还要最小化 \(\max\limits_{(u, v, w) \in E} w\) 。
题意
考虑先构造 \(E\)，有结论：
- 若图中所有联通块大小均为偶数，则存在子图使得所有点度数为奇数。
证明：只需证明联通块数量为 \(1\) 时的情况。若存在一条边 \((x, y)\) 满足断掉 \((x, y)\) 形成的两个联通块大小为偶数，则断掉 \((x, y)\) 并转化为子问题。否则以任意结点 \(rt\) 为根，设 \(siz(x)\) 表示 \(x\) 结点的子树大小，对每个节点讨论（下面设 \(\operatorname{odd}, \operatorname{even}\) 分别表示奇数和偶数）：
- 若 \(x \ne rt\)，则 \(siz(x)\) 与 \(n - siz(x)\) 均为奇数，由于 \(siz(son_x)\) 也是奇数，所以 \(x\) 一定有偶数个儿子，因为 \(\operatorname{even} \times \operatorname{odd} + 1 = \operatorname{odd}\)，并且 \(x\) 与其父亲连有一边，所以 \(deg_x\) 为奇数。
- 若 \(x = rt\)，由于 \(siz(son_x)\) 为奇数，且 \(\operatorname{odd} \times \operatorname{odd} + 1 = \operatorname{even}\)，所以 \(rt\) 一定有奇数个儿子，\(deg_{rt}\) 为奇数。
综上所述，结论得证。
考虑用 LCT 维护，开一个集合维护现在加进来的边，每次新加边后看看能不能少几条集合里的边即可。时间复杂度 \(O(n \log n)\)。
代码
#include <bits/stdc++.h>
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
constexpr int N = 5E5 + 1;
int n, m;
struct Edge {
int fr, to;
int len;
} edge[N];
struct LinkCutTree {
int son[N][2], rev[N], pos[N], fa[N], val[N], sz[N], vsz[N], id[N];
bool checkson(int x) {
return son[fa[x]][1] == x;
}
bool checkroot(int x) {
return son[fa[x]][0] != x && son[fa[x]][1] != x;
}
void pull(int x) {
sz[x] = sz[son[x][0]] + 1 + sz[son[x][1]] + vsz[x];
pos[x] = id[x];
if (edge[pos[son[x][0]]].len > edge[pos[x]].len) {
pos[x] = pos[son[x][0]];
}
if (edge[pos[son[x][1]]].len > edge[pos[x]].len) {
pos[x] = pos[son[x][1]];
}
}
void apply(int x) {
std::swap(son[x][0], son[x][1]);
rev[x] ^= 1;
}
void push(int x) {
if (rev[x]) {
apply(son[x][0]);
apply(son[x][1]);
rev[x] = 0;
}
}
void rotate(int x) {
int y = fa[x], z = fa[y], chy = checkson(y), chx = checkson(x);
if (!checkroot(y)) {
son[z][chy] = x;
}
fa[x] = z;
fa[son[y][chx] = son[x][!chx]] = y;
son[fa[y] = x][!chx] = y;
pull(y);
pull(x);
}
void update(int x) {
if (!checkroot(x)) {
update(fa[x]);
}
push(x);
}
void splay(int x) {
update(x);
while (!checkroot(x)) {
if (!checkroot(fa[x])) {
rotate(checkson(x) != checkson(fa[x]) ? x : fa[x]);
}
rotate(x);
}
pull(x);
}
void access(int x) {
for (int y = 0; x; x = fa[y = x]) {
splay(x);
vsz[x] -= sz[y] - sz[son[x][1]];
son[x][1] = y;
pull(x);
}
}
void makeroot(int x) {
access(x);
splay(x);
apply(x);
}
int findroot(int x) {
access(x);
splay(x);
push(x);
while (son[x][0]) {
x = son[x][0];
push(x);
}
return splay(x), x;
}
void split(int x, int y) {
makeroot(x);
access(y);
splay(y);
}
void link(int u, int v) {
makeroot(u);
if (findroot(v) != u) {
fa[u] = v;
vsz[v] += sz[u];
pull(v);
}
}
void cut(int u, int v) {
split(u, v);
if (!son[u][1] && son[v][0] == u) {
son[v][0] = 0;
fa[u] = 0;
pull(v);
}
}
void addEdge(int i) {
link(edge[i].fr, n + i);
link(n + i, edge[i].to);
}
void cutEdge(int i) {
cut(edge[i].fr, n + i);
cut(edge[i].to, n + i);
vsz[i + n] = 0;
}
bool same(int u, int v) {
return findroot(u) == findroot(v);
}
int query_route(int u, int v) {
split(u, v);
return pos[v];
}
} t;
int check(int x) {
return ((t.sz[x] + 1) / 2) % 2 == 1;
}
int odd_size;
std::set<std::array<int, 2>> edges;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n >> m;
odd_size = n;
for (int i = 1; i <= n + m; ++i) {
if (i <= n) {
t.id[i] = 0;
} else {
t.id[i] = i - n;
}
t.pull(i);
}
for (int i = 1; i <= m; ++i) {
std::cin >> edge[i].fr >> edge[i].to >> edge[i].len;
}
for (int i = 1; i <= m; ++i) {
int u = edge[i].fr, v = edge[i].to, w = edge[i].len;
if (!t.same(u, v)) {
t.makeroot(u);
odd_size -= check(u);
t.makeroot(v);
odd_size -= check(v);
t.addEdge(i);
t.makeroot(u);
odd_size += check(u);
} else {
int p = t.query_route(u, v);
if (w < edge[p].len) {
t.cutEdge(p);
t.addEdge(i);
edges.erase(edges.find({edge[p].len, p}));
} else {
if (odd_size > 0) {
std::cout << -1 << "\n";
} else {
std::cout << (*--edges.end())[0] << "\n";
}
continue;
}
}
edges.insert({w, i});
if (odd_size > 0) {
std::cout << -1 << "\n";
continue;
}
while (true) {
auto [dis, p] = *--edges.end();
int a = edge[p].fr;
int b = edge[p].to;
t.split(a, b);
if (check(a)) {
break;
}
t.cutEdge(p);
edges.erase(*--edges.end());
}
std::cout << (*--edges.end())[0] << "\n";
}
return 0;
}