All Tracks>Problem
Plague Inc.
★★★★★

0

0 votes
Problem

Guess what God’s favourite game is? Plague Inc.! It’s a game where the goal is to infect the whole world with a pathogen you create. Plague Inc. recently rolled out a new update, hence God was eager to play it. However, in his excitement, he forgot to turn on simulation mode…

In this new update, there are n clusters of people. Each cluster is a node, and all these nodes are connected by edges to form a tree. This tree is rooted at node 1. The player can choose a particular node, and infect it. Now, this infection can spread to all the children of this node, which can spread it further. However, the game makes it a little challenging: It can decide to cure random nodes at random times, in which case, all the nodes present in the subtree are cured as well. 

There will be k events in the game. Each event is described by two parameters: the node affected, and the type of event (′I′->Infect, ′C′->Cure). The events are given in a sequential manner. Note that a node can get infected more than once, and similarly, get cured more than once. However, curing a non-infected node does not affect the node, and does not immunize the node to further infections.

At the end of the game, God wanted to find out the number of infected nodes. However, he was devastated when he realised his mistake. As he is busy putting the world back in order, can you help him out?

Note: If a node is cured, even if any of its ancestors are infected at that moment, it won't get infected again, until another succeeding event infects it, directly or indirectly. 

INPUT:

The first line consists of an integer n, the number of nodes.

The next n−1 lines consists of two integers, u and v, denoting that there is an edge between them.

This is followed by an integer k, the number of events.

Then k lines follow, consisting of an integer xi, the affected node, and a character ti, the type of event. ′I′->Infect, ′C′->Cure.

OUTPUT:

Output the number of infected nodes in the end.

CONSTRAINTS:

1≤n,k≤1051≤u,v,xi≤n

ti can be either ‘I’ or ‘S’.

Sample Input
8
1 2
1 3
2 4
2 5
3 6
3 7
4 8
5
1 I
3 C
4 C
2 C
4 I
Sample Output
3
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

Reading events sequentially:

1) 1I -> Root node is infected, hence all nodes 1...8 get infected.

2) 3C -> Node 3 is cured, hence node 6 and 7 also get cured.

3) 4C -> Node 4 is cured, hence node 8 also gets cured.

4) 2C -> Node 2 is cured, hence node 5 gets cured. Nodes 4 and 8 have no effect.

5) 4I -> Node 4 gets infected again, hence node 8 also gets infected.

At the end of the game, 3 nodes are infected (1, 4, 8).

Editor Image

?