Flip Color

4.7

3 votes
C++, Graphs, Algorithms, Depth First Search
Problem

Given an undirected tree with N nodes rooted at node 1, every node is assigned a color which is either black denoted by 1 or white denoted by 0.

We will apply Q operations on the tree as follows:

  • For a given node X and all its ancestors upto the root, flip their colors i.e. if color is white set it to black and vice-versa.

After Q operations on the tree, find the number of nodes which are colored black.

Input

  • First line contains two space separated integers N and Q denoting number of nodes and queries respectively.
  • Second line contains N space separated integers denoting the colors of N nodes.
  • Next N1 lines contains two space separated integers u and v denoting an edge between node u and v.
  • Next line contains Q space-separated integers denoting the node X, for that given operation. 

Output

Print an integer, denoting the number of nodes which are colored black after applying Q operations on the tree.

Constraints

1N,Q1051u,vNuv1XN

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

After first operation on node 2, the color of nodes will be as follows:

  • 0 0 0 1 1, i.e. color of node 2 and 1 will be flipped.

After second operation on node 5, the color of nodes will be as follows:

  • 1 0 0 1 0, i.e. color of node 1 and 5 will be flipped.

Therefore, after Q operations 2 nodes are colored black.

Editor Image

?