Question

c program on Tania is a very joyful child. Sonia gifted her a Tree on her
birthday. Tree has n nodes numbered from 1 to n (rooted at
node 1). Each node can have color either red or black. Initially, all
the nodes are red.
As soon as Tania gets the tree, she starts playing with it. She
performs q operations on the tree. Each operation is described
by 2 integers, an ID (either 1, 2 or 3) and a node P.
Description of the operations are as follows:
ID1: Tania paints red on all the nodes in the subtree of P
(excluding the node P).
• ID2: Tania paints black on all the nodes in the subtree of P
(excluding the node P).
ID3: Tania counts the number of red nodes in the subtree of P
(excluding the node P).
Help her performing operations and print the count of red nodes
as described after each operation of ID3.
Input Format
First line contains a single integer n, the numbers of nodes in
the tree (1 sns 105).
Rules
Next n-1 lines contain 2 space-separated integers x, y(1 sxs
n, 1 sysn, x != y), meaning that there is an edge between x
and y
Finish
Next line contains a single integer q, the numbers of
operations performed on the tree (1 sns 105).
Next a lines contain 2 space-separated integers ID, P(1 SIDS​

Answer 1

Answer:

Run the code

Explanation:

// C++ implementation of the approach

#include <bits/stdc++.h>

using namespace std;

// To store the required answer

int ans = 0;

// To store the graph

vector<int> gr[100005];

// Function to add edges

void Add_Edge(int u, int v)

{

   gr[u].push_back(v);

   gr[v].push_back(u);

}

// Dfs function

void dfs(int child, int par, int color[])

{

   // When there is difference in colors

   if (color[child] != color[par])

       ans++;

   // For all it's child nodes

   for (auto it : gr[child]) {

       if (it == par)

           continue;

       dfs(it, child, color);

   }

}

// Driver code

int main()

{

   // Here zero is for parent of node 1

   int color[] = { 0, 1, 2, 3, 2, 2, 3 };

   // Adding edges in the graph

   Add_Edge(1, 2);

   Add_Edge(1, 3);

   Add_Edge(2, 4);

   Add_Edge(2, 5);

   Add_Edge(3, 6);

   // Dfs call

   dfs(1, 0, color);

   // Required answer

   cout << ans;

   return 0;

}

#SPJ3