当前位置: 首页 > news >正文

D230809E. 勇敢的阿乐

题意:

一个 包含 \(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;
}
http://www.hskmm.com/?act=detail&tid=31095

相关文章:

  • 解码Linux文件IO之标准IO
  • 10.14 CSP-S模拟31 改题记录
  • 高级程序语言第一次作业
  • 安装devc++过程的分享以及问题的记录
  • Linux之线程池 - 指南
  • zlog1
  • LlamaIndex检索调优实战:分块、HyDE、压缩等8个提效方法快速改善答案质量
  • 动火作业风险早预警!AI + 热成像技术筑牢防火安全线
  • 解题报告-P5664 [CSP-S2019] Emiya 家今天的饭
  • object类
  • Day 10
  • 2025 年生态格宾网厂家推荐榜:格宾网石笼/格宾网护坡/格宾网挡墙/格宾网网箱厂家推荐,聚焦工程安全与生态保护,助力基建项目高效落地
  • 时序博弈算法荣获时间检验奖
  • 背叛 仇恨 消极 如刀子刺穿了铁心 嘲笑 嗤之以鼻 漠然后只剩下孤寂
  • STM32主控芯片硬件设计总结
  • 亚马逊因暗黑模式订阅设计支付25亿美元和解金
  • P6645 [CCO 2020] Interval Collection
  • 2025年排烟风机厂家推荐榜:混流风机|管道风机|排烟风机|离心风机|轴流风机|轴流风机厂家,专注高效消防与节能,助力多行业绿色升级
  • 【通达信L2黑科技】 用 DLL 把 10 年机构大单净额 1 秒拖进本地,选股、排序、回测快到飞起!
  • 详细介绍:iCloud照片共享:在家庭内外分享iCloud照片
  • 对static新的认识
  • 2025年氧化镁厂家最新推荐排行榜,电工级/高温/低温/中温/防火电缆/矿物绝缘/熔盐加热器/电热管用/单头管用/合成云母用氧化镁公司推荐!
  • 智能体分析
  • 2025 年玄武岩厂家推荐榜:玄武岩/0-3mm/3-5mm/5-10mm/10-15mm/10-20mm/石子厂,聚焦基建升级与高端化需求,山东展飞建筑材料有限公司成优选
  • 2025 佛山铝合金/系统/断桥铝/耐用/推拉/封阳台/别墅/静音门窗厂家品牌实力推荐:聚焦技术与服务的五大优选标杆
  • Ubuntu22.04 server网络配置
  • 完整教程:深度学习优化器全面指南:核心参数选择与实战策略
  • 说说新版畅联云的一些重要约定
  • App.vue(完整可运行示例)
  • Windows MySQL 报错