CF603E Pastoral Oddities

CF603E Pastoral Oddities

There exists a set of edges such that every point has an odd degree,A sufficient condition is that the number of points of connected blocks is even.

Consider necessity first,Add side degrees and increase $2$ So the sum of degrees is even,And when the number of connected blocks that satisfy the condition is odd,The sum of degrees must be odd,矛盾.

证明充分性：for an even-sized connected block,Find one of its spanning trees,Starting from the leaf, consider whether to add it to the father's edge according to the degree to the son,Gradually satisfy,Finally, all conditions are met except the root,Obviously the condition is also satisfied according to the parity root,So sufficiency is guaranteed.

Therefore, it is possible to maintain whether the connected block satisfies the condition by merging and checking the set by rank.

Then consider the restriction that the largest edge weight in the edge set is the smallest,A minimum spanning tree is sufficient.

在线 LCT Maintain a minimum spanning tree forest,时间复杂度 $\mathcal{O}(n\log n)$.

But it's very hard to write and the constants are huge,考虑离线做法.

Observe the samples,时间升序,The answer is monotonically decreasing;还有“最大值最小”一类的词,考虑二分.

多次询问,考虑整体二分.

具体地,Discretize weights,Then divide and conquer the weights,令其为 $mid$.

Add weights $\le mid$ side until legal,Divide and conquer according to the first legal position.

注意细节,The state behind the overall bisection $(l,r,vl,vr)$ All numbers are required to be included in the merge set $\le l$ 且权值 $\le vl$ 的边,Consider maintaining an undoable and lookup set.

时间复杂度 $\mathcal{O}(m\log m\log n)$.

#include<cstdio>
#include<algorithm>

typedef long long ll;

#define ha putchar(' ')
#define he putchar('\n')

inline int read() {
    
	int x = 0;
	char c = getchar();
	while (c < '0' || c > '9')
		c = getchar();
	while (c >= '0' && c <= '9')
		x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	return x;
}

inline void write(int x) {
    
	if (x < 0) {
    
		putchar('-');
		x = -x;
	}
	if (x > 9)
		write(x / 10);
	putchar(x % 10 + 48);
}

const int _ = 3e5 + 5;

int n, m, cnt, fa[_], sz[_], t, s[_], ans[_];

struct abc {
    
	int u, v, w, id;
	bool operator < (const abc &t) {
    
		return w < t.w;
	}
} e[_], b[_];

int find(int x) {
    
	return fa[x] == x ? x : find(fa[x]);
}

void merge(int u, int v) {
    
	u = find(u), v = find(v);
	if (u == v) return;
	if (sz[u] < sz[v]) std::swap(u, v);
	if ((sz[u] & 1) && (sz[v] & 1)) cnt -= 2;
	sz[u] += sz[v], fa[v] = u, s[++t] = v;
}

void ers(int lim) {
    
	while (t > lim) {
    
		int v = s[t--], u = fa[v];
		fa[v] = v, sz[u] -= sz[v];
		if ((sz[u] & 1) && (sz[v] & 1)) cnt += 2;
	}
}

void solve(int l, int r, int vl, int vr) {
    
	if (l > r || vl > vr) return;
	if (vl == vr) {
    
		for (int i = l; i <= r; ++i) ans[i] = b[vl].w;
		return;
	}
	int mid = (vl + vr) >> 1, nw = t;
	for (int i = vl; i <= mid; ++i)
		if (b[i].id < l) merge(b[i].u, b[i].v);
	int Id = r + 1, nw2 = t;
	for (int i = l; i <= r; ++i) {
    
		if (e[i].w <= b[mid].w) merge(e[i].u, e[i].v);
		if (!cnt) {
    
			Id = i;
			break;
		}
	}
	ers(nw2);
	solve(l, Id - 1, mid + 1, vr);
	ers(nw);
	for (int i = l; i < Id; ++i)
		if (e[i].w <= b[vl].w) merge(e[i].u, e[i].v);
	solve(Id, r, vl, mid);
	ers(nw);
}

signed main() {
    
	n = cnt = read(), m = read();
	for (int i = 1; i <= n; ++i) fa[i] = i, sz[i] = 1;
	for (int i = 1; i <= m; ++i) {
    
		e[i].u = read(), e[i].v = read(), e[i].w = read();
		e[i].id = i, b[i] = e[i];
	}
	std::sort(b + 1, b + m + 1);
	b[m + 1].w = -1;
	solve(1, m, 1, m + 1);
	for (int i = 1; i <= m; ++i) write(ans[i]), he;
}