Flip Color
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 \(N-1\) 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
\(1 \le N, Q \le 10^5 \\ 1 \leq u,v \leq N \\ u \neq v \\ 1 \leq X \leq N\)
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.
