铺路[jzoj6491]

发表于 分类于

题意

problem

题解

首先来分析一波：

我们发现，当所有的点的度数都为奇数时，点数必定是偶数。

证明可以用归纳法。

考虑一棵偶数个点的树，它一定符合所有点的度数为奇数。

那么对于一个偶数个点的图，我们保留它的一棵最小生成树，最小生成树中最大的边权就是答案了。

考虑 $n,m\leq 2000$ 的做法，也就是只考虑一次询问时该怎么做。

可以将边从小到大排好序，然后一个一个插进去。直到所有连通块的点数都是偶数，当前这条边的权值就是答案。

那么你获得了一个 $O(n^2\alpha(n))$ 的50分做法。

接下来考虑正解：

方法1

考虑继续沿用50分做法的思想，不考虑离线，直接做。

显然答案是单调不降的。

那么对于当前的生成森林，你如果删掉了权值最大的边后，这条边就以后都不可能再加回去了。

考虑用LCT维护这个生成森林，每次尝试插进一条新的边，如果插进去以后形成了环，那么将环上的最大的边删掉。

然后如果此时连通块均为偶数，我们则可以考虑去删最大的边。

那么我们维护一个可删堆，每次在堆中找到还生成森林里面的最大的边，直到删掉之后连通块出现了奇数。

需要在LCT中维护子树大小以及链的最大边。

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

程序

方法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <bitset>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
const int N=400010;
const int inf=1e9+7;
namespace LCT{
	int fa[N],ch[N][2],siz[N],si[N],val[N],mi[N];
	bool r[N];
	inline bool son(int x) {return ch[fa[x]][1]==x;}
	inline bool isroot(int x) {return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}
	inline int getmax(int x,int y)
	{
		return val[x]<=val[y]?y:x;
	}
	inline void pushup(int x)
	{
		siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+si[x]+(val[x]==-inf);
		mi[x]=getmax(x,getmax(mi[ch[x][0]],mi[ch[x][1]]));
	}
	inline void rev(int x)
	{
		if(!x) return;
		r[x]^=1;
		swap(ch[x][0],ch[x][1]);
	}
	inline void pushdown(int x)
	{
		if(!r[x]) return;
		r[x]=0;
		rev(ch[x][0]); rev(ch[x][1]);
	}
	inline void push(int x){if(!isroot(x)) push(fa[x]); pushdown(x);}
	inline void rotate(int x)
	{
		int y=fa[x],z=fa[y],d=son(x);
		if(!isroot(y)) ch[z][son(y)]=x; fa[x]=z;
		ch[y][d]=ch[x][1-d]; fa[ch[y][d]]=y;
		ch[x][1-d]=y; fa[y]=x;
		pushup(y);
	}
	inline void splay(int x)
	{
		push(x);
		for(int y=fa[x];!isroot(x);rotate(x),y=fa[x])
			if(!isroot(y)) rotate((son(x)^son(y))?x:y);
		pushup(x);
	}
	inline void access(int x)
	{
		for(int y=0;x;y=x,x=fa[x])
		{
			splay(x);
			si[x]+=siz[ch[x][1]]-siz[y];
			ch[x][1]=y;
			pushup(x);
		}
	}
	inline void makeroot(int x) {access(x); splay(x); rev(x);}
	inline void split(int x,int y) {makeroot(x); access(y); splay(y);}
	inline void link(int x,int y)
	{
		split(x,y); fa[x]=y; si[y]+=siz[x]; pushup(y);
	}
	inline void cut(int x,int y)
	{
		split(x,y); ch[y][0]=fa[x]=0;
	}
	inline int findroot(int x)
	{
		access(x); splay(x);
		for(;ch[x][0];pushdown(x),x=ch[x][0]);
		return x;
	}
	inline int findsiz(int x)
	{
		access(x); splay(x); return siz[x];
	}
	inline int findmax(int x,int y)
	{
		split(x,y);
		return mi[y];
	}
}
using namespace LCT;
struct cmp{
	inline bool operator () (const int &x,const int &y) {return (val[x]==val[y])?x<y:val[x]<val[y];}
};
struct del_queue{
	priority_queue<int,vector<int>,cmp> q1,q2;
	inline void push(int x)
	{
		q1.push(x);
	}
	inline void pop(int x)
	{
		q2.push(x);
	}
	inline int top()
	{
		for(;!q1.empty()&&!q2.empty();)
		{
			if(q1.top()==q2.top()) q1.pop(),q2.pop();
			else break;
		}
		if(q1.empty()) return -1;
		else return q1.top();
	}
	inline bool empty()
	{
		return q1.size()==q2.size();
	}
}p;
int cnt,n,m,X[N],Y[N],fx,fy,x,y,z,sum;
inline void del()
{
	for(int u;!p.empty();)
	{
		u=p.top();
		cut(X[u],u);
		if(findsiz(X[u])&1) return (void)(link(X[u],u));
		cut(Y[u],u);
		p.pop(u);
	}
}
int main()
{
	FO(road);
	sum=cnt=n=read(); m=read();
	val[0]=-inf-1; siz[0]=0;
	fo(i,1,n) mi[i]=i,val[i]=-inf,siz[i]=1;
	fo(i,1,m)
	{
		x=read(),y=read(); ++cnt; val[cnt]=z=read(); mi[cnt]=cnt;
		X[cnt]=x; Y[cnt]=y;
		fx=findroot(x); fy=findroot(y);
		if(fx!=fy)
		{
			sum-=(findsiz(fx)&1)+(findsiz(fy)&1);
			link(x,cnt); link(y,cnt);
			sum+=(findsiz(cnt)&1);
			p.push(cnt);
		}
		else
		{
			int k;
			k=findmax(x,y);
			if(val[k]>z)
			{
				cut(X[k],k),cut(Y[k],k);
				p.pop(k);
				link(x,cnt); link(y,cnt);
				p.push(cnt);
			}
		}
		if(!sum) del();
		printf("%d\n",sum?-1:val[p.top()]);
	}
	return 0;
}