Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Tahsin and Tree

By CLown1331 · Limits 1s, 512 MB

Tahsin loves graph theory very much. He is specialy fond of trees. For his upcoming birthday his friends decided to gift him a tree, lets call it birthday tree. Birthday tree consists of n node numbered 1 to n, having a light in every node. Initialy some of the light is turned on and some are turned off. Root of the tree is 1.

The tree has a special property, when a node is toggled, all the children of the node is also toggled. So if you toggle the node i, you also toggle the children of i and so on.

In order to help Tahsin understand the tree better, you are going help him process q queries.


Input starts with T ( 1 <= T <= 5 ).

The first line of every test contains two integers n and q. ( 1 <= n < q <= 105 ). The second line contains n integer a1, a2, ..., an, where ai is the initial state of the node i. Each of the next n-1 lines contains two integer ui, vi, ( 1 <= ui, vi <= n ), meaning there is an edge between ui and vi.

Each of the next q line contains an integer x ( 1 <= x <= n ), the node to be toggled.


n, q ( 1 <= n < q <= 100000 ).


For each case, after processing all the queries, print n integer b1, b2, ..., bn, denoting the status of the node.

See the sample test case for input output format.


4 1
0 1 1 0 
1 4
2 1
3 1

Case 1: 1 0 0 1



86% Solution Ratio

shaheen_bdEarliest, Oct '17

edge555Fastest, 0.2s

a.salamLightest, 5.1 MB

SoudipShortest, 818B


Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.