首页 > 代码库 > codeforces717E Paint it really, really dark gray(树上dfs)
codeforces717E Paint it really, really dark gray(树上dfs)
题意:
给你一棵树,2e5个节点,每个节点有一种颜色(黑色或粉色)
让你从节点1开始,自由沿边行走,到达节点时会把这个节点的颜色改变
要求你输出任意一条路径使得从节点1出发,所有节点的颜色都变为黑色
思路:
很明显要递归遍历
每到达一个节点就先改变节点的颜色标志并输出当前节点
如果当前到达了叶子节点,则不用进行操作
返回上层节点时再改变节点的颜色标志并输出当前节点,然后判断叶子节点的颜色,如果为粉色,则再到达一次叶子节点再回到当前节点
这样确保当前节点的所有儿子节点都为黑色的
然后就这样一直递归到根节点1,判断根节点的颜色
如果为黑色(其实这代表着根节点为粉色,因为刚进入dfs的时候根节点的颜色被改变了一次,但是那次是不算改变的,所以颜色正好相反了)
则去他的儿子节点(儿子粉)再回来(根黑)再去那个儿子节点(儿子黑)这样就使得所有的节点都是黑色的了
如果为粉色的话就直接不用操作了,已经完成了要求
/* *********************************************** Author :devil ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <stack> #include <map> #include <string> #include <cmath> #include <stdlib.h> #define LL long long #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,a,b) for(int i=a;i>=b;i--) #define ou(a) printf("%d\n",a) #define pb push_back #define mkp make_pair template<class T>inline void rd(T &x) { char c=getchar(); x=0; while(!isdigit(c))c=getchar(); while(isdigit(c)) { x=x*10+c-‘0‘; c=getchar(); } } #define IN freopen("in.txt","r",stdin); #define OUT freopen("out.txt","w",stdout); using namespace std; const int inf=0x3f3f3f3f; const int mod=1e9+7; const int N=2e5+10; vector<int>eg[N]; bool a[N]; void fun(int u) { a[u]^=1; printf("%d ",u); } void dfs(int u,int fa) { fun(u); for(int i=0;i<eg[u].size();i++) { int v=eg[u][i]; if(v==fa) continue; dfs(v,u); fun(u); if(a[v]) fun(v),fun(u); } if(u==1&&!a[u]) fun(eg[u][0]),fun(u),fun(eg[u][0]); } int main() { #ifndef ONLINE_JUDGE IN #endif int n,x,y; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&x); a[i]=x==-1?1:0; } for(int i=1;i<n;i++) { scanf("%d%d",&x,&y); eg[x].pb(y); eg[y].pb(x); } dfs(1,0); return 0; }
codeforces717E Paint it really, really dark gray(树上dfs)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。