CodeForces 717E

Paint it really, really dark gray

题面

time limit per test:1 second

memory limit per test:256 megabytes

input:standard input

output:standard output

I see a pink boar and I want it painted black. Black boars look much more awesome and mighty than the pink ones. Since Jaggy became the ruler of the forest, he has been trying his best to improve the diplomatic relations between the forest region and the nearby ones.

Some other rulers, however, have requested too much in return for peace between their two regions, so he realized he has to resort to intimidation. Once a delegate for diplomatic relations of a neighboring region visits Jaggy’s forest, if they see a whole bunch of black boars, they might suddenly change their mind about attacking Jaggy. Black boars are really scary, after all.

Jaggy’s forest can be represented as a tree (connected graph without cycles) with n vertices. Each vertex represents a boar and is colored either black or pink. Jaggy has sent a squirrel to travel through the forest and paint all the boars black. The squirrel, however, is quite unusually trained and while it traverses the graph, it changes the color of every vertex it visits, regardless of its initial color: pink vertices become black and black vertices become pink.

Since Jaggy is too busy to plan the squirrel’s route, he needs your help. He wants you to construct a walk through the tree starting from vertex 1 such that in the end all vertices are black. A walk is a sequence of vertices, such that every consecutive pair has an edge between them in a tree.

Input

The first line of input contains integer n (2 ≤ n ≤ 200 000), denoting the number of vertices in the tree. The following n lines contains nintegers, which represent the color of the nodes.

If the i-th integer is 1, if the i-th vertex is black and  - 1 if the i-th vertex is pink.

Each of the next n - 1 lines contains two integers, which represent the indexes of the vertices which are connected by the edge. Vertices are numbered starting with 1.

Output

Output path of a squirrel: output a sequence of visited nodes’ indexes in order of visiting. In case of all the nodes are initially black, you should print 1. Solution is guaranteed to exist. If there are multiple solutions to the problem you can output any of them provided length of sequence is not longer than $10^7$.

Sample Input

1
2
3
4
5
6
7
8
9
10
5
1
1
-1
1
-1
2 5
4 3
2 4
4 1

Sample Output

1
1 4 2 5 2 4 3 4 1 4 1

Note

At the beginning squirrel is at node 1 and its color is black. Next steps are as follows:

  • From node 1 we walk to node 4 and change its color to pink.
  • From node 4 we walk to node 2 and change its color to pink.
  • From node 2 we walk to node 5 and change its color to black.
  • From node 5 we return to node 2 and change its color to black.
  • From node 2 we walk to node 4 and change its color to black.
  • We visit node 3 and change its color to black.
  • We visit node 4 and change its color to pink.
  • We visit node 1 and change its color to pink.
  • We visit node 4 and change its color to black.
  • We visit node 1 and change its color to black.

题目大意

一棵树,1号点为根,每个点有1或-1的权值。

要求从根出发,每到一个点该点权值变为相反数,求一条路径使得所有节点权值均为正。

P.S.一开始从1出发时,1号节点权值不变,以后再到时改变。

思路

贪心

对于每个节点打一个标记,即以该节点为根的子树若有需要修改的点,则标记为true,否则标记为false

然后到达一个节点时,若它的子节点有true标记,则先修改该子节点为根的子树,然后再修改当前节点。

这里需要注意一点,对于每个节点需要判断两次。

​ 一次是修改以子节点为根的子树(不包括子节点)

​ 一次是专门修改子节点

这里修改某一节点可以通过$father→son→father$来将$son$的标记取相反数。

注意1号节点的情况需要特殊判断,假设除1号节点外所有节点均修改好,当前位置在1号节点,1号节点仍需修改

​ 那么假设2为1的一个子节点,通过$2→1→2$操作即可完成

题目保证有解!

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <iostream>
#include <cstring>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <deque>
#include <bitset>
#include <algorithm>

using namespace std;

const double eps=1e-10;
const double pi=3.1415926535897932384626433832795;
const double eln=2.718281828459045235360287471352;

#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define scan2(x, y) scanf("%d%d", &x, &y)
#define scan3(x, y, z) scanf("%d%d%d", &x, &y, &z)
#define sqr(x) (x) * (x)
#define pr(x) printf("Case %d: ",x)
#define prn(x) printf("Case %d:\n",x)
#define prr(x) printf("Case #%d: ",x)
#define prrn(x) printf("Case #%d:\n",x)
#define lowbit(x) (x&(-x))

const int maxn=200005;

vector<int> g[maxn];
int fat[maxn];
vector<int> son[maxn];
int now[maxn];
bool has[maxn];
int i,j,k,n;

struct hi
{
int num;
void pri(int t)
{
num++;
if(num>1)printf(" ");
printf("%d",t);
}
}q;

void DFS(int x,int y)
{
fat[x]=y;
if(now[x]<0)has[x]=true;
for(unsigned int i=0;i<g[x].size();i++)
{
int v=g[x][i];
if(fat[v]!=0)continue;
son[x].push_back(v);
DFS(v,x);
if(now[v]<0 || has[v])has[x]=true;
}
}

void find(int x)
{
q.pri(x);
if(x>1)now[x]=-now[x];
if(son[x].size()==0){has[x]=false;return;}
for(unsigned int i=0;i<son[x].size();i++)
{
int v=son[x][i];
if(has[v]){find(v);now[x]=-now[x];q.pri(x);}
}
for(unsigned int i=0;i<son[x].size();i++)
{
int v=son[x][i];
if(has[v]){find(v);now[x]=-now[x];q.pri(x);}
}
if(now[x]<0)has[x]=true;else has[x]=false;
if(x==1 && has[x])
{
q.pri(son[1][0]);
q.pri(x);
q.pri(son[1][0]);
}
}

int main()
{
scanf("%d",&n);
memset(has,0,sizeof(has));
for(i=1;i<=n;i++)scanf("%d",&now[i]);
for(i=1;i<=n-1;i++)
{
scan2(j,k);
g[j].push_back(k);
g[k].push_back(j);
}
DFS(1,-1);
q.num=0;
find(1);n=0;
return 0;
}