树上贪心+生成树贪心：1104T3

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134235828

<47.92.197.167:5283/contest/425/problem/3>

根据 nn 奇偶性可以推断答案

合法解只需要在任何一棵生成树上构造即可

贪心肯定要在最大生成树上

然后从前往后看一条未选的边能不能选即可

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
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//srand(time(0));
#define N 900010
//#define M
//#define mo
int n, m, i, j, k;
int c[N], ans[N], u, v, mn[N], f[N], cho[N]; 
vector<pair<int, int> >G[N], T; 

int fa(int x) {
	if(f[x]==x) return x; 
	return f[x]=fa(f[x]); 
}

void dfs1(int x, int fa, int id) {
	for(auto t : G[x]) {
		int y=t.fi, i=t.se; 
		if(y==fa) continue; 
		debug("%d -> %d (%d)\n", x, y, i); 
		dfs1(y, x, i); 
	}
	if(fa && c[x]%2==0) c[x]++, c[fa]++, ans[id]=1; 
}

void dfs2(int x, int fa) {
	for(auto t : G[x]) {
		int y=t.fi, id=t.se; 
		if(y==fa) continue; 
		mn[y]=id; dfs2(y, x); 
		mn[x]=min(mn[x], mn[y]); 
	}
}

int dfs3(int x, int fa, int id) {
	cho[x]=1e9; 
	if(id!=1e9 && ans[id]==0) cho[x]=id; 
	if(id==mn[x]) {
		if(ans[id]==1) return 1e9; 
		else cho[x]=id; 
	}
	for(auto t : G[x]) {
		int y=t.fi, i=t.se; 
		if(y==fa) continue;  
		dfs3(y, x, i); 
		debug("# %lld -> %lld\n", x, y); 
		cho[x]=min(cho[x], cho[y]); 
//		if(k!=1e9) break;
	}
	if(id<cho[x] && ans[id]==1) return cho[x]=1e9; 
//	debug("%lld : %lld | %d || %d\n", x, flg, id, mn[x]); 
//	if(flg && id<=m) ans[id]^=1; 
	return cho[x]; 
}

void dfs4(int x, int fa, int id) {
	if(cho[x]==1e9) return ; 
	sort(G[x].begin(), G[x].end(), [&] (pair<int, int>x, pair<int, int>y) { return cho[x.fi]<cho[y.fi]; }); 
	for(auto t : G[x]) {
		int y=t.fi, i=t.se; 
		if(y==fa) continue; 
		dfs4(y, x, i); break; 
	}
	if(cho[x]!=1e9 && fa)  ans[id]^=1; 
}

signed main()
{
//	freopen("lilac.in", "r", stdin);
//	freopen("lilac.out", "w", stdout);
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	T=read();
//	while(T--) {
//
//	}
	n=read(); m=read(); 
	for(i=1; i<=m; ++i) {
		u=read()+1; v=read()+1; 
		debug("%d %d\n", u, v); 
		T.pb({u, v}); 
	}
	for(i=1; i<=n; ++i) f[i]=i; 
	for(i=m-1; i>=0; --i) {
		auto t=T[i]; 
		u=t.fi; v=t.se; 
		if(fa(u)==fa(v)) { ans[i+1]=1; ++c[u]; ++c[v]; continue; }
		f[fa(u)]=fa(v); 
		G[u].pb({v, i+1}); G[v].pb({u, i+1}); 
	}
	for(i=1; i<=m; ++i) debug("%d", ans[i]); debug("\n"); 
	for(i=1; i<=n; ++i) debug("%d ", c[i]); debug("\n"); 
	dfs1(1, 0, 0); 
	if(n%2==0) { 
		for(i=1; i<=m; ++i) printf("%d", ans[i]); 
		return 0; 
	}
	mn[1]=1e9; dfs2(1, 0); 
	for(i=1; i<=n; ++i) debug("%d ", mn[i]); debug("\n"); 
	for(i=1; i<=m; ++i) debug("%d", ans[i]); debug("\n"); 
	dfs3(1, 0, 1e9); 
	for(i=1; i<=m; ++i) debug("%d ", cho[i]); debug("\n"); 
	dfs4(1, 0, 1e9); 
	for(i=1; i<=m; ++i) printf("%d", ans[i]); 
	return 0;
}