「CodeForces - 717E」Paint it really, really dark gray (dfs)
2024-10-11 11:37:50
BUPT 2017 summer training (for 16) #1H
题意
每个节点是黑色or白色,经过一个节点就会改变它的颜色,一开始在1节点。求一条路径使得所有点变成黑色。
题解
dfs时每个节点的孩子处理完,这时候如果颜色是白色,那么再去一下父亲节点再回来,就变成黑色了。
如果是1号点,那就去它的孩子节点,再回来,再去它孩子节点。
代码
#include <cstdio>
#define N 200005
struct edge{
int to,next;
}e[N<<1];
int head[N],cnt;
int n,a[N];
void add(int u,int v){
e[++cnt]=(edge){v,head[u]};
head[u]=cnt;
}
int ans[N<<1],top;
void dfs(int x,int fa){
ans[++top]=x;
a[x]*=-1;
for(int i=head[x];i;i=e[i].next){
int v=e[i].to;
if(v==fa)continue;
dfs(v,x);
ans[++top]=x;
a[x]*=-1;
}
if(a[x]==-1){
if(x!=1){
ans[++top]=fa;
a[fa]*=-1;
ans[++top]=x;
a[x]=1;
}else{
ans[++top]=e[head[1]].to;
ans[++top]=1;
ans[++top]=e[head[1]].to;
}
}
}
int main(){
scanf("%d",&n);
bool ex=0;
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
if(a[i]==-1)
ex=1;
}
for(int i=1,u,v;i<n;++i){
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
if(!ex)printf("1");
else{
a[1]*=-1;
dfs(1,0);
for(int i=1;i<=top;++i)
printf("%d ",ans[i]);
}
return 0;
}
最新文章
- 我想立刻辞职,然后闭关学习编程语言,我给自己3个月时间学习C语言!这样行的通吗
- android 获取屏幕宽度和高度
- python中文分词:结巴分词
- maven_spring mvc_mina_dome(实体,文件,批传)(spring mina 初学dome)
- SQLServer 列出每个表的列和属性
- (转载)IOS中UIScrollView的属性和委托方法
- Angular自动双向绑定值
- box-shadow使用指南
- [core java学习笔记][第四章对象与类]
- osg项目经验1<;MFC+OSG中模型点选效果>;
- cinder块存储控制节点
- Python中什么时候使用生成器?
- 【原】Java学习笔记028 - 集合
- 3D GIS 应用开发 —— 基于 Mapbox GL 的实践总结
- jquery常用语句
- Linux环境下虚拟环境virtualenv安装和使用
- 网易云通过KCSP认证,云原生技术实力再获认可
- 10 个 MySQL 经典错误【转】
- Atitit 支出分类表 会计科目(1)资产(2)负债(3)资本(4)收益(5)费用(成本) 资产分类表 attilax总结
- Java之相对路径找不到文件问题解决方法
热门文章
- Sparse Principal Component Analysis
- mysql 小数转换成百分数查出(保留两位小数百分数)
- 泛函p121可分Hilbert空间都同构于l^2
- Python_线程、线程效率测试、数据隔离测试、主线程和子线程
- js中的一些方法
- Is there a way to avoid undeployment memory leaks in Tomcat?
- 配置react-sass
- apach ab 安装时的错误
- [转帖]csdn windows 下载整理.
- 【学亮IT手记】使用Map代替switch...case语句