<span>codeforces717E Paint it really, really dark gray（树上dfs）</span>
题意：
给你一棵树，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; }
