题意:
一个 包含 \(n\) 个点 \(m\) 条边的简单无向连通图。现在,删掉其中的一些边让度数为奇数的点尽可能多。
输出要删掉哪些边, 用一个长为 \(m\) 的 01串
表示, 第 \(i\) 位为 \(1\) 表示不删第 \(i\) 条边, 为 \(0\) 表示删掉第 \(i\) 条边。并满足这个 01串
的字典序尽量大。
对于 \(100 \%\) 的数据, \(2 \leq n \leq 6 * 10^{5}, n-1 \leq m \leq 9 * 10^{5}, 0 \leq x_{i} \leq y_{i}<n\), 对任意 \(i \neq j\), 有 \(\left(x_{i}, y_{i}\right) \neq\left(x_{j}, y_{j}\right)\), 且保证给定的图连通。
题解:
先考虑是树有什么性质。若点数为偶数,那么度数为偶数的点必然有偶数个。因为度数和一直为偶数。
那么我们可以考虑任意两两偶数点配对,其路径上所有边状态翻转。那么这样答案是一定的。因为考虑一个边子树内的情况,若子树内有偶数个度数为偶数的点,那么其外侧也会有偶数个度数为偶数的点,那么一定会越过这条边偶数次,反之则一定是奇数次,所以是确定的。
根据这一点,我们可以快速判断每个点的状态,只需要记录子树内部的度数为偶数的点的和即可,我们把这个东西给成点权,这样方便做题。
接下来考虑奇数个点的情况,先还是判断每条边是否可能删除。但是注意,这时候我们构造出来的东西就不大一样了,我们在 dfs
中让子树内部的度数为偶数的点的和为偶数的点保留,其他删除,那么最终 \(1\) 号点的度数一定为偶数,其他都是奇数。因为递归的时候还是保持的相同策略,所以结果不变。
这样虽然满足了度数为奇数的点尽可能多,但是没有满足字典序尽量大,考虑处理这个东西。
我们思考怎么改变答案,就是让 \(1\to u\) 链上翻转一下,看这个答案是否比原来大。可以树剖线段树 \(+\) hash 来做这玩意,但是我们有更好的方法。
我们按照边的编号从小到大搞,这个时候我们能不删除就不删除,显然满足了题意。考虑若出现了要删除的边,考虑能否换掉原来度数为偶数的点,使其不用删掉。这时我们进行分类。
设原来的点为 \(h\) 现在的点为 \(v\),那么我们已经翻转了 \(1\to h\) 的点权。
\(v\) 对应的边本来要删掉:
- 若 \(v\) 为 \(h\) 的祖先,那么自然不用删了,因为翻转了。
- 若 \(v\) 和 \(h\) 没有祖先后代关系,那么该删就要删。
- 若 \(v\) 在 \(h\) 子树内但是 \(1\to v\) 的路径上有编号比 \(v\) 小的点是没有删的,那么我们还是要删这一点,因为不删前面更小的边就要保留了,不符合贪心。
- 若 \(v\) 在 \(h\) 子树且 \(1\to v\) 的路径上所有编号比 \(v\) 小的点都删除了,我们翻转边权并让 \(h=v\)。
\(v\) 对应的边本来要保留:
-
若 \(v\) 是 \(h\) 的祖先,那么翻转了,必须删掉。
-
否则我们保留,并且将其记录下来,表示没有删除。
接下来考虑图,其实很简单,我们都证明了答案最大只要是树就可以,那我们让图上挖一颗树,使得其最小编号最大,这不就是最大生成树吗,所以还是在树上做。
code:
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define lbt(x) (x&(-x))
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int N=2e6+10;
int n,m,k,T,a[N],fa[N],out[N],dfn[N];
int cnt,t[N],val[N],ans[N],vv[N],idx[N];
vector<pii> g[N];struct node{int u,v;}e[N];
int find(int x){if(fa[x]==x) return x;return fa[x]=find(fa[x]);
}
int dfs(int u,int fa){dfn[u]=++cnt;int nw=0;for(pii t:g[u]){int v=t.fi,id=t.se;if(v==fa) continue;int p=dfs(v,u);if(!p) ans[id]=1;nw+=p;idx[id]=v;}out[u]=cnt;return (((val[u]&1)^1)+nw)&1;
}
void upd(int i,int x){while(i<N){t[i]+=x;i+=lbt(i);}}
int sc(int i){int ans=0;while(i>0){ans+=t[i];i-=lbt(i);}return ans;}
signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>m;rep(i,1,n) fa[i]=i;rep(i,1,m){int x,y;cin>>x>>y;e[i]={x+1,y+1};}per(i,m,1){int u=e[i].u,v=e[i].v;val[u]++,val[v]++;if(find(u)!=find(v)){vv[i]=1;fa[find(u)]=find(v);g[u].pb({v,i});g[v].pb({u,i}); }else ans[i]=1;}dfs(1,0);if(n%2==0){rep(i,1,m) cout<<ans[i];}else{int h=1;rep(i,1,m){int v=idx[i];if(!vv[i]){cout<<1;continue;}if(!ans[i]){if(dfn[v]<=dfn[h]&&dfn[h]<=out[v]){cout<<1;continue;}if(dfn[v]<dfn[h]||out[h]<dfn[v]||sc(dfn[v])>0) cout<<0;else h=v,cout<<1;}else{if(dfn[h]<dfn[v]||out[v]<dfn[h]){cout<<1;upd(dfn[v],1);upd(out[v]+1,-1);}else cout<<0;}}}return 0;
}